fork download
copy 
  1. //#####   #####   #####   #####   #####   #       #####   #   #//
  2. //#   #   #   #   #       #       #   #   #       #   #   ## ##//
  3. //#####   #####   #####   #       #####   #       #####   # # #//
  4. //##      #   #       #   #       #   #   #       #   #   #   #//
  5. //# #     #   #       #   #       #   #   #       #   #   #   #//
  6. //#  #    #   #       #   #       #   #   #       #   #   #   #//
  7. //#   #   #   #   #####   #####   #   #   #####   #   #   #   #//
  8.  
  9.  
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12. #define ll long long
  13. #define mod 1000000007
  14. #define pb push_back
  15. #define ppb pop_back
  16. #define cs(n) cout<<n<<" "
  17. #define cn(n) cout<<n<<"\n"
  18. #define rep(i,j,k) for(int i=j;i<k;i++)
  19. #define rrep(i,j,k) for(int i=j;i>=k;i--)
  20. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  21. #define N 100005
  22. #define stime s1time
  23. int n;
  24. vector<int>v[N];
  25. int totka = 0;
  26. int stime[N];
  27. int etime[N];
  28. int ftree[2 * N];
  29. int par[N];
  30. int lca[N][20];
  31. int val[N];
  32. int level[N];
  33. bool visited[N] = {0};
  34. int freq[N] = {0};
  35. int colfreq[N] = {0};
  36. int blk = 0;
  37. map<int , bool>mp;
  38. ll bin(ll a, ll b)
  39. {
  40. 	if (b == 0)
  41. 		return 1;
  42. 	if (b % 2 == 0)
  43. 		return bin((a * a) % mod , b / 2) % mod;
  44. 	return ((a % mod) * (bin((a * a) % mod , b / 2) % mod)) % mod;
  45. }
  46. bool comp(pair<pair<int , int>, pair<pair<int , int> , int> > a, pair<pair<int , int>, pair<pair<int , int> , int> > b) {
  47. 	if (a.first.first / blk != b.first.first)
  48. 		return a.first.first < b.first.first;
  49. 	return a.first.second < b.first.second;
  50. }
  51. void dfs(int i , int l , int p) {
  52. 	par[i] = p;
  53. 	level[i] = l;
  54. 	totka++;
  55. 	stime[i] = totka;
  56. 	ftree[totka] = i;
  57. 	visited[i] = true;
  58. 	for (auto k : v[i]) {
  59. 		if (visited[k] == false)
  60. 			dfs(k, l + 1, i);
  61. 	}
  62. 	totka++;
  63. 	etime[i] = totka;
  64. 	ftree[totka] = i;
  65. }
  66. int la(int a, int b) {
  67. 	if (level[a] > level[b]) {
  68. 		swap(a, b);
  69. 	}
  70. 	int l = level[b] - level[a];
  71. 	while (l > 0) {
  72. 		int j = log2(l);
  73. 		b = lca[b][j];
  74. 		l -= bin(2, j);
  75. 	}
  76. 	if (a == b) {
  77. 		return a;
  78. 	}
  79. 	rrep(i, 19, 0) {
  80. 		if (lca[a][i] != -1 && lca[b][i] != -1 && lca[a][i] != lca[b][i]) {
  81. 			a = lca[a][i];
  82. 			b = lca[b][i];
  83. 		}
  84. 	}
  85. 	return par[a];
  86. }
  87. void add(int a) {
  88. 	freq[a]++;
  89. 	if (freq[a] == 1) {
  90. 		colfreq[val[a]]++;
  91. 	}
  92. 	else if (freq[a] == 2) {
  93. 		colfreq[val[a]]--;
  94. 	}
  95. }
  96. void remove(int a) {
  97. 	freq[a]--;
  98. 	if (freq[a] == 0) {
  99. 		colfreq[val[a]]--;
  100. 	}
  101. 	else if (freq[a] == 1) {
  102. 		colfreq[val[a]]++;
  103. 	}
  104. }
  105. void solve()
  106. {
  107. 	int m;
  108. 	cin >> m;
  109. 	double ieou = ceil(sqrt(2 * n));
  110. 	totka = 0;
  111. 	rep(i, 0, n) {
  112. 		v[i].clear();
  113. 	}
  114. 	memset(visited, 0, sizeof(visited));
  115. 	memset(freq, 0, sizeof(freq));
  116. 	memset(colfreq, 0, sizeof(colfreq));
  117. 	blk = (int)ieou;
  118. 	rep(i, 1, n + 1)
  119. 	cin >> val[i];
  120. 	rep(i, 0, n - 1) {
  121. 		int a, b;
  122. 		cin >> a >> b;
  123. 		v[a].pb(b);
  124. 		v[b].pb(a);
  125. 	}
  126. 	dfs(1, 0, -1);
  127. 	memset(lca, -1, sizeof(lca));
  128. 	rep(i, 0, 20) {
  129. 		rep(j, 1, n + 1) {
  130. 			if (i == 0) {
  131. 				lca[j][i] = par[j];
  132. 			}
  133. 			else {
  134. 				if (lca[j][i - 1] == -1)
  135. 					lca[j][i] = -1;
  136. 				else
  137. 					lca[j][i] = lca[lca[j][i - 1]][i - 1];
  138. 			}
  139. 		}
  140. 	}
  141. 	vector<pair<pair<int , int>, pair<pair<int , int> , int> > >v1;
  142. 	rep(i, 1, m + 1) {
  143. 		int a, b, c;
  144. 		cin >> a >> b >> c;
  145. 		int d = la(a, b);
  146. 		if (d != a && d != b) {
  147. 			if (stime[a] > stime[b]) {
  148. 				swap(a, b);
  149. 			}
  150. 			v1.pb({{etime[a], stime[b]}, {{d, c}, i}});
  151. 		}
  152. 		else {
  153. 			if (stime[a] > stime[b]) {
  154. 				swap(a, b);
  155. 			}
  156. 			v1.pb({{stime[a], stime[b]}, {{ -1, c}, i}});
  157. 		}
  158. 	}
  159. 	sort(v1.begin(), v1.end(), comp);
  160. 	int ml = 1, mr = 0;
  161. 	rep(i, 0, v1.size()) {
  162. 		int l = v1[i].first.first;
  163. 		int r = v1[i].first.second;
  164. 		while (mr < r) {
  165. 			mr++;
  166. 			add(ftree[mr]);
  167. 		}
  168. 		while (l < ml) {
  169. 			ml--;
  170. 			add(ftree[ml]);
  171. 		}
  172. 		while (r < mr) {
  173. 			remove(ftree[mr]);
  174. 			mr--;
  175. 		}
  176. 		while (l > ml) {
  177. 			remove(ftree[ml]);
  178. 			ml++;
  179. 		}
  180. 		int c = v1[i].second.first.first;
  181. 		int f = v1[i].second.first.second;
  182. 		if (c != -1) {
  183. 			if (f == val[c] || colfreq[f] > 0)
  184. 				mp[v1[i].second.second] = true;
  185. 			else
  186. 				mp[v1[i].second.second] = false;
  187. 		}
  188. 		else {
  189. 			if (colfreq[f] > 0)
  190. 				mp[v1[i].second.second] = true;
  191. 			else
  192. 				mp[v1[i].second.second] = false;
  193. 		}
  194. 	}
  195. 	rep(i, 1, m + 1) {
  196. 		if (mp[i])
  197. 			cout << "Find" << "\n";
  198. 		else
  199. 			cout << "NotFind" << "\n";
  200. 	}
  201. }
  202. int main()
  203. {
  204. #ifndef ONLINE_JUDGE
  205. 	freopen("input.txt", "r" , stdin);
  206. 	freopen("output.txt" , "w" , stdout);
  207. #endif
  208. 	fastio;
  209. 	int t;
  210. 	//cin >> t;
  211. 	t = 0;
  212. 	while (cin >> n)
  213. 	{
  214. 		if (t > 0) {
  215. 			cout << endl;
  216. 		}
  217. 		solve();
  218. 		t++;
  219. 	}
  220. 	return 0;
  221. }
Success #stdin #stdout 0s 14592KB
comments (?)
stdin
copy 
5 5
1 2 3 4 5
1 2
1 3
3 4
3 5
2 3 4
2 4 3
2 4 5
4 5 1
4 5 3
stdout
copy 
NotFind
Find
NotFind
NotFind
Find
https://ideone.com/wS8EZH
problem GOT, based on SPOJ submission 26178641 (CPP14), 2020-06-21 20:56:56
language:
C++14 (gcc 8.3)
created:
3 years 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!