fork download
copy 
  1. //teja349
  2. #include <bits/stdc++.h>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <string>
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <climits>
  10. #include <utility>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <queue>
  14. #include <stack>
  15. #include <iomanip>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp> 
  18. //setbase - cout << setbase (16); cout << 100 << endl; Prints 64
  19. //setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
  20. //setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
  21. //cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
  22.  
  23. using namespace std;
  24. using namespace __gnu_pbds;
  25.  
  26. #define f(i,a,b) for(i=a;i<b;i++)
  27. #define rep(i,n) f(i,0,n)
  28. #define fd(i,a,b) for(i=a;i>=b;i--)
  29. #define pb push_back
  30. #define mp make_pair
  31. #define vi vector< int >
  32. #define vl vector< ll >
  33. #define ss second
  34. #define ff first
  35. #define ll long long
  36. #define pii pair< int,int >
  37. #define pll pair< ll,ll >
  38. #define sz(a) a.size()
  39. #define inf (1000*1000*1000+5)
  40. #define all(a) a.begin(),a.end()
  41. #define tri pair<int,pii>
  42. #define vii vector<pii>
  43. #define vll vector<pll>
  44. #define viii vector<tri>
  45. #define mod (1000*1000*1000+7)
  46. #define pqueue priority_queue< int >
  47. #define pdqueue priority_queue< int,vi ,greater< int > >
  48. #define flush fflush(stdout) 
  49. #define primeDEN 727999983
  50. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  51.  
  52. // find_by_order()  // order_of_key
  53. typedef tree<
  54. int,
  55. null_type,
  56. less<int>,
  57. rb_tree_tag,
  58. tree_order_statistics_node_update>
  59. ordered_set;
  60.  
  61. vector< set<int> > adj(212345);
  62.  
  63. int subtree[212345];
  64. int query(int val){
  65. 	cout<<1<<" "<<val<<endl;
  66. 	fflush(stdout);
  67. 	cin>>val;
  68. 	return val;
  69. }
  70.  
  71. int dfs(int cur,int par){
  72. 	set<int>::iterator it;
  73. 	//cout<<cur<<" "<<par<<endl;
  74. 	subtree[cur]=1;
  75. 	for(it=adj[cur].begin();it!=adj[cur].end();it++){
  76. 		if(*it==par)
  77. 			continue;
  78. 		dfs(*it,cur);
  79. 		subtree[cur]+=subtree[*it];
  80. 	}
  81.  
  82. 	return 0;
  83. }
  84. int findcentroid(int cur,int par,int req){
  85. 	set<int>::iterator it;
  86. 	for(it=adj[cur].begin();it!=adj[cur].end();it++){
  87. 		if(*it==par)
  88. 			continue;
  89. 		if(subtree[*it]>req){
  90. 			return findcentroid(*it,cur,req);
  91. 		}
  92. 	}
  93. 	return cur;
  94. }
  95. int solve(int cur){
  96. 	dfs(cur,-1);
  97. 	int val=findcentroid(cur,-1,subtree[cur]/2);
  98. 	//cout<<"centroid "<<subtree[cur]<<endl;
  99. 	int gg=query(val);
  100. 	if(gg==-1)
  101. 		return val;
  102. 	else{
  103. 		adj[gg].erase(val);
  104. 		return solve(gg);
  105. 	}
  106.  
  107.  
  108. }
  109. int main(){
  110.     std::ios::sync_with_stdio(false); cin.tie(NULL);
  111. 	int t;
  112. 	cin>>t;
  113. 	while(t--){
  114. 		int n;
  115. 		cin>>n;
  116. 		int i;
  117. 		int u,v;
  118. 		rep(i,n+10){
  119. 			adj[i].clear();
  120. 		}
  121. 		rep(i,n-1){
  122. 			cin>>u>>v;
  123. 			adj[u].insert(v);
  124. 			adj[v].insert(u);
  125. 		}
  126. 		int ans=solve(1);
  127. 		cout<<2<<" "<<ans<<endl;
  128. 		cin>>ans;
  129. 		fflush(stdout);
  130. 	}
  131.     return 0;   
  132. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BIArI4
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!