fork download 
  1. #include<bits/stdc++.h>
  2. #define pi pair<int, int>
  3. #define ppi pair<pi, pi>
  4. #define f first
  5. #define s second
  6. using namespace std;
  7.  
  8. const int N=100005;
  9. int n, m, q, u, v, os, pu, pv, wu, wv, idx;
  10. map<string, int> sid;
  11. string st, su, sv;
  12. int mom[N], W[N], pw[N], tw[N]={0};
  13.  
  14.  
  15. inline pi par(int x){
  16. 	int wu=0;
  17. 	while(x!=mom[x]){
  18. 		wu^=pw[x];
  19. 		x=mom[x];
  20. 	}
  21. 	return pi(x, wu);
  22. }
  23.  
  24. int main(){
  25. 	std::ios_base::sync_with_stdio(false);
  26. 	cin.tie(0);
  27.  
  28. 	cin>>n>>m>>q;
  29.  
  30. 	for(int i=0; i<n; i++){
  31. 		cin>>st;
  32. 		sid[st]=i;
  33. 		mom[i]=i;
  34. 		W[i]=1;
  35. 	}
  36.  
  37. 	pi tmp;
  38. 	for(int i=0; i<m; i++){
  39. 		cin>>os>>su>>sv;
  40. 		u=sid[su];
  41. 		v=sid[sv];
  42. 		os--;
  43. 		tmp=par(u);
  44. 		pu=tmp.f; wu=tmp.s;
  45. 		tmp=par(v);
  46. 		pv=tmp.f; wv=tmp.s;
  47.  
  48. 		if(pu!=pv){
  49. 			if(W[u]>W[v]){
  50. 				mom[pv]=pu;
  51. 				W[pu]+=W[pv];
  52. 				pw[pv]=os^wu^wv;
  53. 			}
  54. 			else{
  55. 				mom[pu]=pv;
  56. 				W[pv]+=W[pu];
  57. 				pw[pu]=os^wu^wv;
  58. 			}
  59. 			cout<<"YES\n";
  60. 		}
  61. 		else{
  62. 			if(wu^wv==os){
  63. 				cout<<"YES\n";
  64. 			}
  65. 			else cout<<"NO\n";
  66. 		}
  67. 	}
  68.  
  69. 	for(int i=0; i<n; i++){
  70. 		u=i;
  71. 		while(u!=mom[u]){
  72. 			tw[i]^=pw[u];
  73. 			u=mom[u];
  74. 		}
  75. 	}
  76.  
  77. 	for(int i=0; i<q; i++){
  78. 		cin>>su>>sv;
  79. 		u=sid[su];
  80. 		v=sid[sv];
  81. 		if(par(u).f!=par(v).f){
  82. 			cout<<"3\n";
  83. 		}
  84. 		else if(tw[u]^tw[v]==0){
  85. 			cout<<"1\n";
  86. 		}
  87. 		else{
  88. 			cout<<"2\n";
  89. 		}
  90. 	}
  91.  
  92. }
  93.  
Success #stdin #stdout 0s 5028KB
comments (?)
stdin 
3 3 4
hate love like
1 love like
2 love hate
1 hate like
love like
love hate
like hate
hate like
stdout 
YES
YES
NO
1
2
2
2
https://ideone.com/EhwB7S
language:
C++14 (gcc 8.3)
created:
7 years 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!