fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 1e7+5;
  4. using ll = long long;
  5. int par[MAXN+1];
  6. int rnk[MAXN+1];
  7.  
  8. void make(int v){
  9. 	par[v]=v;
  10. 	rnk[v]=0;
  11. }
  12.  
  13. int findPar(int v){
  14. 	if(v == par[v])return v;
  15. 	return par[v] = findPar(par[v]);
  16. }
  17.  
  18. void unite(int a1 ,int b1){
  19. 	int a = findPar(a1);
  20. 	int b = findPar(b1);
  21.  
  22. if(a == b){return;}
  23. 	if(rnk[a]<rnk[b])swap(a,b);
  24.  
  25.  
  26.     par[b]=a;
  27. 	if(rnk[a]==rnk[b])rnk[a]+=1;
  28. }
  29. struct Edge{
  30. 	ll w;
  31. 	ll u,v;
  32. 	bool operator<(const Edge &other)const{
  33. 		return w<other.w;
  34. 	};
  35. };
  36.  
  37. struct Query{
  38. 	ll mw;
  39. 	ll u,v;
  40. 	ll idx;
  41.  
  42. 		bool operator<(const Query &other)const{
  43. 		return mw<other.mw;
  44. 	};
  45. };
  46. int main() {
  47. 	int t;
  48. 	cin>>t;
  49. 	while(t--){
  50.    int n,m,q ;
  51.    cin>>n>>m>>q;
  52.  
  53.    for(int i = 0;i<n ;i++){
  54.    	make(i);
  55.    }
  56.    vector<Edge>edges(m);
  57.  for(int i = 0;i<m ;i++){
  58.  	cin>>edges[i].u>>edges[i].v>>edges[i].w;
  59.  }
  60.  vector<Query>query(q);
  61.  for(int i = 0;i<q;i++){
  62.  	cin>>query[i].u>>query[i].v>>query[i].mw;
  63.  	query[i].idx = i;
  64.  }
  65.  sort(edges.begin(),edges.end());
  66.  sort(query.begin(),query.end());
  67.  
  68.  vector<ll>ans(q+1,0);
  69.  ll ei = 0;
  70.  for(ll i = 0 ;i<q;i++){
  71.  	const Query &curr = query[i];
  72.  
  73.  	while(ei<m && edges[ei].w<curr.mw){
  74.  		unite(edges[ei].u,edges[ei].v);
  75.  		ei++;
  76.  	}
  77.  
  78.  	if(findPar(curr.u) == findPar(curr.v)){
  79.  		ans[curr.idx]=1;
  80.  	}
  81.  }
  82.  
  83.     for(int i = 0 ;i<q;i++){
  84.     	cout<<ans[i]<<endl;
  85.     }
  86. 	}
  87. 	return 0;
  88. }
Success #stdin #stdout 0.01s 5620KB
comments (?)
stdin
copy 
1
4 3 3
0 1 2
1 2 5
2 3 8
0 2 6
0 3 5
1 3 10
stdout
copy 
1
0
1
https://ideone.com/VE8awl
language:
C++14 (gcc 8.3)
created:
10 hours ago
visibility:
public

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!