1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 502 struct Z { int v, cost; bool operator < (const Z &p) const { return p.cost<cost; } }; Z z, z2; int shortest[MX], forbidden[MX][MX]; vector<Z> adj[MX]; vector<int> parent[MX]; priority_queue<Z>pq; int dijkstra(int src, int dst, int node) { for(int i=0; i<node; i++) shortest[i]=1e9; z.v = src; z.cost = 0; pq.push(z); shortest[src]=0; while(!pq.empty()) { z = pq.top(); pq.pop(); int l = adj[z.v].size(); for(int i=0; i<l; i++) { z2 = adj[z.v][i]; if(forbidden[z.v][z2.v]==1) continue; if(shortest[z2.v]>shortest[z.v]+z2.cost) { parent[z2.v].clear(); parent[z2.v].push_back(z.v); z2.cost = shortest[z2.v]= shortest[z.v]+z2.cost; pq.push(z2); } else if(shortest[z2.v]==shortest[z.v]+z2.cost) parent[z2.v].push_back(z.v); } } return shortest[dst]; } void removeEdge(int src, int dst) { if(dst==src) return; for(int i=0;i<parent[dst].size();i++) { forbidden[ parent[dst][i] ][dst] = 1; removeEdge(src, parent[dst][i]); } return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int tc,kk=1, node, edge, u, v, cost, src, dst; while(cin>>node>>edge && node) { cin>>src>>dst; for(int i=0; i<edge; i++) { cin>>u>>v>>cost; z.v = v; z.cost = cost; adj[u].push_back(z); } int tmp = 1e9; int mn = dijkstra(src, dst, node); //initial if(mn<1e9) { removeEdge(src, dst); //remove edges of shortest tmp = dijkstra(src, dst, node); //second time } if(tmp==1e9) tmp = -1; cout<<tmp<<endl; CLR(forbidden); for(int i=0;i<node;i++) { adj[i].clear(); parent[i].clear(); } } return 0; } |
Sunday, 18 June 2017
Almost Shortest Path (UVa 12144, UVaLive 4210, Regionals 2008 >> Latin America - South America)
Thursday, 8 June 2017
Reverse Integer (LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution { public: int reverse(int x) { bool flag = false; if(x<0) { flag = true; x*=-1; } int rev = 0; while(x) { if((rev*10)/10 != rev) return 0; // checking overflow rev = rev*10 + x%10; x/=10; } if(flag) rev*=-1; return rev; } }; |
Median of Two Sorted Arrays (LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int l1 = nums1.size(); int l2 = nums2.size(); if(l1>l2) return findMedianSortedArrays(nums2, nums1); int k = (l1+l2-1)>>1; int lft = 0, rgt = l1; while(lft<rgt) { int md = (lft+rgt)>>1; if(nums1[md]<nums2[k-md]) lft = md+1; else rgt = md; } double x, y; if(lft>0 && (k-lft)>=0) x = max(nums1[lft-1], nums2[k-lft]); else if(lft>0) x = nums1[lft-1]; else if(k-lft>=0) x = nums2[k-lft]; if((l1+l2) & 1) return x; //total odd size, single median if(lft<l1 && (k-lft+1)<l2) y = min(nums1[lft], nums2[k-lft+1]); else if(lft<l1) y = nums1[lft]; else if((k-lft+1)<l2) y = nums2[k-lft+1]; return (x+y)/2.0; } }; |
Sunday, 4 June 2017
Football (UVa 12673, UVaLive 6530, Regionals 2013 >> Latin America)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 struct match{ int score, receive; bool operator < (const match &m) const{ return m.score-m.receive < score-receive ; } }; match mth[MX]; int main() { ios_base::sync_with_stdio(0);cin.tie(0); int tc,kk=1, n, g; //cin>>tc; while(cin>>n>>g) { for(int i=0;i<n;i++) cin>>mth[i].score>>mth[i].receive; sort(mth, mth+n); int point = 0; for(int i=0;i<n;i++) { //cout<<mth[i].score<<" "<<mth[i].receive<<endl; if(mth[i].score>mth[i].receive) point += 3; else if(mth[i].score==mth[i].receive) { if(g>0) { point += 3; g--; } else point += 1; } else if(mth[i].score<mth[i].receive) { if(g>(mth[i].receive-mth[i].score)) { point += 3; g= g-(mth[i].receive-mth[i].score)-1; } else if(g==(mth[i].receive-mth[i].score)) { point += 1; g= g-(mth[i].receive-mth[i].score); } } } cout<<point<<endl; } return 0; } |
Saturday, 3 June 2017
Proving Equivalences (UVa 12167, UVaLive 4287, Regionals 2008 >> Europe - Northwestern)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 vector<int>adj[20002]; stack<int>stk; int t, lo[20002], tim[20002], vis[20002], sccrm[20002], scc, done; void tarjan_scc(int u) { t++; vis[u]=1; lo[u]=tim[u]=t; stk.push(u); for(int i=0;i<adj[u].size();i++) { int v = adj[u][i]; if(!vis[v]) { tarjan_scc(v); lo[u]=min(lo[u], lo[v]); } else if(vis[v]==1) lo[u]=min(lo[u], tim[v]); } if(lo[u]==tim[u]) { scc++; do{ done = stk.top(); stk.pop(); sccrm[done]=scc; vis[done]=2; }while(done!=u); } return; } int main() { ios_base::sync_with_stdio(0);cin.tie(0); int kk=1, tc, n, m, u, v; string s; cin>>tc; while(tc--) { cin>>n>>m; t=scc=0; while(!stk.empty()) stk.pop(); for(int i=1;i<=n;i++) { adj[i].clear(); vis[i]=0; } while(m--) { cin>>u>>v; adj[u].push_back(v); } for(int i=1;i<=n;i++) if(!vis[i]) tarjan_scc(i); // checking zero indegree and outdegree of scc bool hasIndegree[scc+2], hasOutdegree[scc+2]; CLR(hasIndegree); CLR(hasOutdegree); for(int i=1;i<=n;i++) for(int j=0;j<adj[i].size();j++) if(sccrm[i]!=sccrm[adj[i][j]]) //not in same scc { hasIndegree[sccrm[i]]=true; hasOutdegree[sccrm[adj[i][j]]]=true; } int zeroIndgree=0, zeroOutdegree=0; for(int i=1;i<=scc;i++) { if(!hasIndegree[i]) zeroIndgree++; if(!hasOutdegree[i]) zeroOutdegree++; } if(scc==1) cout<<0<<endl; else cout<<max(zeroIndgree, zeroOutdegree)<<endl; //cout<<"Case "<<kk++<<": "<< <<"\n"; } return 0; } |
Thursday, 1 June 2017
Interval Product (UVa 12532, UVaLive 6139, Regionals 2012 >> Latin America)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | /// Raihan Ruhin /// CSE, Jahangirnagar University. /// Dhaka-Bangladesh. /// id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj) /// mail: raihanruhin@ (yahoo / gmail / facebook) /// blog: ruhinraihan.blogspot.com #include<bits/stdc++.h> using namespace std; #define SET(a) memset(a,-1,sizeof(a)) #define CLR(a) memset(a,0,sizeof(a)) #define PI acos(-1.0) #define MOD 1000000007 #define MX 100010 int z1, z2, node[MX*4]; void insert(int idx, int st, int ed, int s, int e, int val) { if(st==s && ed==e) { if(val>0) node[idx]=1; else if(val<0) node[idx]=-1; else node[idx]=0; return; } int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1; if(e<=mid) insert(lft, st, mid, s, e, val); else if(s>mid) insert(rgt, mid+1, ed, s, e, val); else { insert(lft, st, mid, s, mid, val); insert(rgt, mid+1, ed, mid+1, e, val); } node[idx] = node[lft] * node[rgt]; return; } int query(int idx, int st, int ed, int s, int e) { if(st==s && ed==e) { return node[idx]; } int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1; if(e<=mid) return query(lft, st, mid, s, e); else if(s>mid) return query(rgt, mid+1, ed, s, e); else return query(lft, st, mid, s, mid)*query(rgt, mid+1, ed, mid+1, e); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int tc,kk=1, n, q, x, y; char c; string s; while(cin>>n>>q) { for(int i=1;i<=n*4;i++) node[i]=1; for(int i=1; i<=n; i++) { cin>>x; insert(1, 1, n, i, i, x); } while(q--) { cin>>c>>x>>y; if(c=='C') insert(1, 1, n, x, x, y); else { z1 = query(1, 1, n, x, y); //cout<<z1.pos<<" "<<z1.neg<<" "<<z1.zero<<endl; if(z1==0) cout<<"0"; else if(z1<0) cout<<"-"; else cout<<"+"; } } cout<<endl; } return 0; } |
Subscribe to:
Posts (Atom)