fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fst first
  3. #define snd second
  4. #define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
  5. #define pb push_back
  6. #define ALL(s) s.begin(),s.end()
  7. #define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  8. #define SZ(s) int(s.size())
  9. using namespace std;
  10. typedef long long ll;
  11. typedef pair<int,int> ii;
  12.  
  13. const int MAXN=10010;
  14. int can[MAXN];
  15.  
  16. struct UnionFind {
  17. 	int n,comp;
  18. 	vector<int> uf,si,c;
  19. 	UnionFind(int n=0):n(n),comp(n),uf(n),si(n,1){
  20. 		fore(i,0,n)uf[i]=i;}
  21. 	int find(int x){return x==uf[x]?x:find(uf[x]);}
  22. 	bool join(int x, int y){
  23. 		if((x=find(x))==(y=find(y)))return false;
  24. 		if(si[x]<si[y])swap(x,y);
  25. 		si[x]+=si[y];uf[y]=x;comp--;c.pb(y);
  26. 		return true;
  27. 	}
  28. 	int snap(){return c.size();}
  29. 	void rollback(int snap){
  30. 		while(c.size()>snap){
  31. 			int x=c.back();c.pop_back();
  32. 			si[uf[x]]-=si[x];uf[x]=x;comp++;
  33. 		}
  34. 	}
  35. };
  36. enum {ADD,DEL,QUERY};
  37. struct Query {int type,x,y,id;};
  38. struct DynCon {
  39. 	vector<Query> q;
  40. 	UnionFind dsu;
  41. 	vector<int> mt;
  42. 	map<pair<int,int>,int> last;
  43. 	DynCon(int n):dsu(n){}
  44. 	void add(int x, int y){
  45. 		if(x>y)swap(x,y);
  46. 		q.pb((Query){ADD,x,y,-1});mt.pb(-1);last[{x,y}]=q.size()-1;
  47. 	}
  48. 	void remove(int x, int y){
  49. 		if(x>y)swap(x,y);
  50. 		q.pb((Query){DEL,x,y,-1});
  51. 		int pr=last[{x,y}];mt[pr]=q.size()-1;mt.pb(pr);
  52. 	}
  53. 	void query(int x, int y,int id){q.pb((Query){QUERY,x,y,id});mt.pb(-1);}
  54. 	void process(){ // answers all queries in order
  55. 		if(!q.size())return;
  56. 		fore(i,0,q.size())if(q[i].type==ADD&&mt[i]<0)mt[i]=q.size();
  57. 		go(0,q.size());
  58. 	}
  59. 	void go(int s, int e){
  60. 		if(s+1==e){
  61. 			if(q[s].type==QUERY){
  62. 				can[q[s].id]|=dsu.find(q[s].x)==dsu.find(q[s].y);
  63. 			}
  64. 			return;
  65. 		}
  66. 		int k=dsu.snap(),m=(s+e)/2;
  67. 		for(int i=e-1;i>=m;--i)if(mt[i]>=0&&mt[i]<s)dsu.join(q[i].x,q[i].y);
  68. 		go(s,m);dsu.rollback(k);
  69. 		for(int i=m-1;i>=s;--i)if(mt[i]>=e)dsu.join(q[i].x,q[i].y);
  70. 		go(m,e);dsu.rollback(k);
  71. 	}
  72. };
  73.  
  74. int p[MAXN];
  75. int find(int x){return p[x]=p[x]==x?x:find(p[x]);}
  76. void join(int x, int y){p[find(x)]=find(y);}
  77.  
  78. vector<pair<ii,int>> eds[MAXN],qss[MAXN];
  79. vector<int> cols[MAXN],wh[MAXN];
  80. vector<ii> g[MAXN];
  81. int rep[MAXN],repcol[MAXN];
  82.  
  83. void doit(int id){
  84. 	vector<pair<ii,int>> ed=eds[id], qs=qss[id];
  85. 	fore(i,0,SZ(wh[id])) rep[wh[id][i]]=i;
  86. 	fore(i,0,SZ(cols[id])) repcol[cols[id][i]]=i;
  87.  
  88. 	for(auto &e:ed){
  89. 		e.fst.fst=rep[e.fst.fst];
  90. 		e.fst.snd=rep[e.fst.snd];
  91. 		e.snd=repcol[e.snd];
  92. 	}
  93. 	for(auto &q:qs) q.fst.fst=rep[q.fst.fst], q.fst.snd=rep[q.fst.snd];
  94.  
  95. 	int n=SZ(wh[id]),k=SZ(cols[id]);
  96.  
  97. 	vector<vector<ii>> v(k);
  98. 	for(auto e:ed) v[e.snd].pb(e.fst);
  99.  
  100. 	DynCon dc(n);
  101.  
  102. 	fore(i,0,k) for(auto x:v[i]) dc.add(x.fst,x.snd);
  103.  
  104. 	fore(i,0,k){
  105. 		for(auto x:v[i]) dc.remove(x.fst,x.snd);
  106. 		for(auto q:qs) dc.query(q.fst.fst, q.fst.snd, q.snd);
  107. 		for(auto x:v[i]) dc.add(x.fst,x.snd);
  108. 	}
  109.  
  110. 	dc.process();
  111.  
  112. 	for(auto q:qs) can[q.snd]|=k%2;
  113. }
  114.  
  115. int main(){FIN;
  116. 	int t,tt=1; cin>>t;
  117. 	while(t--){
  118. 		int n,m,q; cin>>n>>m>>q;
  119.  
  120. 		fore(i,0,n){
  121. 			g[i].clear();
  122. 			cols[i].clear();
  123. 			wh[i].clear();
  124. 			eds[i].clear();
  125. 			p[i]=i;
  126. 		}
  127.  
  128. 		fore(i,0,q){
  129. 			qss[i].clear();
  130. 		}
  131.  
  132. 		fore(i,0,q) can[i]=0;
  133.  
  134. 		vector<pair<ii,int>> ed;
  135.  
  136. 		fore(i,0,m){
  137. 			int x,y,w; cin>>x>>y>>w; x--; y--;
  138. 			ed.pb({{x,y},w});
  139. 			join(x,y);
  140. 		}
  141.  
  142. 		for(auto e:ed) eds[find(e.fst.fst)].pb(e), cols[find(e.fst.fst)].pb(e.snd);
  143.  
  144. 		fore(i,0,n){
  145. 			sort(ALL(cols[i]));
  146. 			cols[i].erase(unique(ALL(cols[i])),cols[i].end());
  147. 		}
  148. 		fore(i,0,n) wh[find(i)].pb(i);
  149.  
  150. 		fore(i,0,n) sort(ALL(wh[i]));
  151.  
  152. 		fore(i,0,q){
  153. 			int x,y; cin>>x>>y; x--; y--;
  154. 			if(find(x)==find(y)) qss[find(x)].pb({{x,y},i});
  155. 		}
  156.  
  157.  
  158. 		fore(i,0,n) if(find(i)==i) doit(i);
  159.  
  160. 		int res=0;
  161. 		fore(i,0,q) res+=can[i];
  162.  
  163. 		cout<<"Case #"<<tt++<<": "<<res<<"\n";
  164. 	}
  165. }
Runtime error #stdin #stdout 0.01s 5456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/saMRhj
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!