fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. int ask(int v) {
  8. 	cout << "1 " << v + 1 << endl;
  9. 	int x;
  10. 	cin >> x;
  11. 	if(x == -1) {
  12. 		cout << "2 " << v + 1 << endl;
  13. 		int t;
  14. 		cin >> t;
  15. 		return -1;
  16. 	}
  17. 	return x - 1;
  18. };
  19.  
  20. vector<vector<int>> g;
  21. vector<int> size, block;
  22.  
  23. void dfs(int v, int p) {
  24. 	size[v] = 1;
  25. 	for(auto u: g[v]) {
  26. 		if(u != p && !block[u]) {
  27. 			dfs(u, v);
  28. 			size[v] += size[u];
  29. 		}
  30. 	}
  31. }
  32. int get(int v, int p, int n) {
  33. 	for(auto u: g[v]) {
  34. 		if(u != p && 2 * size[u] > n && !block[u]) {
  35. 			return get(u, v, n);
  36. 		}
  37. 	}
  38. 	return v;
  39. }
  40.  
  41. int find_centroid(int v, int p) {
  42. 	fill(begin(size), end(size), 0);
  43. 	dfs(v, p);
  44. 	return get(v, p, size[v]);
  45. }
  46.  
  47. void solve() {
  48. 	int n;
  49. 	cin >> n;
  50. 	g.assign(n, vector<int>());
  51. 	size.assign(n, 0);
  52. 	block.assign(n, 0);
  53. 	for(int i = 1; i < n; i++) {
  54. 		int x, y;
  55. 		cin >> x >> y;
  56. 		x--, y--;
  57. 		g[x].push_back(y);
  58. 		g[y].push_back(x);
  59. 	}
  60. 	int v = find_centroid(0, 0);
  61. 	while(true) {
  62. 		int u = ask(v);
  63. 		if(u != -1) {
  64. 			block[v] = 1;
  65. 			v = find_centroid(u, v);
  66. 		} else {
  67. 			break;
  68. 		}
  69. 	}
  70. }
  71.  
  72. signed main() {
  73. 	//freopen("input.txt", "r", stdin);
  74. 	ios::sync_with_stdio(0);
  75. 	cin.tie(0);
  76. 	int t;
  77. 	cin >> t;
  78. 	while(t--) {
  79. 		solve();
  80. 	}
  81. 	return 0;
  82. }
  83.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Q1OZvK
language:
C++14 (gcc 8.3)
created:
5 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!