Advertisement
GerONSo

J 100

Jan 11th, 2020
253
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.74 KB | None | 0 0
  1. /*
  2.  
  3. ∧_∧
  4. ( ・ω・。)つ━☆・*。
  5. ⊂  ノ    ・゜
  6. しーJ   Accepted
  7.  
  8. */
  9.  
  10.  
  11.  
  12. // #pragma GCC optimize("O3")
  13. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  14.  
  15. #include <bits/stdc++.h>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18.  
  19. #define ll long long
  20. #define all(x) begin(x), end(x)
  21. #define x first
  22. #define y second
  23. // #define int long long
  24.  
  25. using namespace std;
  26. using namespace __gnu_pbds;
  27.  
  28. typedef long double ld;
  29. template<typename T>
  30. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31.  
  32. const ld PI = atan2(0, -1);
  33.  
  34. void seriy() {
  35. ios::sync_with_stdio(0);
  36. cin.tie(0);
  37. cout.tie(0);
  38. cout << fixed << setprecision(14);
  39. #ifdef _offline
  40. // freopen("input.txt", "r", stdin);
  41. freopen("output.txt", "w", stderr);
  42. #endif
  43. }
  44.  
  45. const int MAXN = 1e6 + 10;
  46. const int MAXM = 600;
  47. const int INF = 1e9 + 7;
  48. const int BASE = 47;
  49. const int MOD = 1e9 + 7;
  50. const int MAXLOG = 51;
  51. const ld EPS = 1e-6;
  52.  
  53. vector<vector<int>> g;
  54. vector<int> op, lul;
  55. vector<int> used;
  56. int cur = 0, last;
  57.  
  58. void dfs(int u, int p) {
  59. // euler.push_back(cur);
  60. last++;
  61. op[cur] = u;
  62. lul[u] = cur;
  63. cur++;
  64. for(auto v : g[u]) {
  65. if(v != p) {
  66. dfs(v, u);
  67. }
  68. }
  69. // euler.push_back(cur);
  70. }
  71.  
  72. signed main() {
  73. seriy();
  74. int n;
  75. cin >> n;
  76. g.resize(n);
  77. used.resize(n);
  78. lul.resize(n);
  79. op.resize(n);
  80. for(int i = 0; i < n - 1; i++) {
  81. int u, v;
  82. cin >> u >> v;
  83. u--;
  84. v--;
  85. g[u].push_back(v);
  86. g[v].push_back(u);
  87. }
  88.  
  89. // for(auto i : op) {
  90. // cout << i << " ";
  91. // }
  92. while(1) {
  93. char c;
  94. cin >> c;
  95. if(c == 'E') {
  96. break;
  97. }
  98. for(int i = 0; i < n; i++) {
  99. sort(all(g[i]), [&](int a, int b) {
  100. return used[a] > used[b] || used[a] == used[b] && a < b;
  101. });
  102. }
  103. last = 0;
  104. cur = 0;
  105. int first = 0;
  106. for(int i = 0; i < n; i++) {
  107. lul[i] = i;
  108. }
  109. for(int i = 0; i < n; i++) {
  110. sort(all(g[i]), [&](int a, int b) {
  111. return lul[a] < lul[b];
  112. });
  113. }
  114. dfs(0, -1);
  115. fill(all(used), 0);
  116. set<int> res;
  117. int CNT = 10;
  118. last = n;
  119. int lol = -1;
  120. while(CNT--) {
  121. // cerr << last << " " << lol << '\n' << '\n';
  122. // for(auto i : op) {
  123. // cerr << i << " " << used[i] << '\n';
  124. // }
  125. // cerr << '\n';
  126. // cerr << CNT << '\n';
  127. int cnt = 0;
  128. int pos_f = -1;
  129. for(int i = 0; i < n; i++) {
  130. if(op[i] == first) {
  131. pos_f = i;
  132. }
  133. }
  134. int l = -1, r = n;
  135. while(r - l > 1) {
  136. int mid = (r + l) >> 1;
  137. set<int> kek;
  138. for(int j = 0; j <= mid; j++) {
  139. kek.insert(op[j]);
  140. }
  141. // for(auto j : res) {
  142. // kek.insert(j);
  143. // }
  144. cout << "? " << kek.size() << " ";
  145. cnt++;
  146. for(auto i : kek) {
  147. // assert(i != -1);
  148. cout << i + 1 << " ";
  149. }
  150. cout << endl;
  151. int ans;
  152. cin >> ans;
  153. assert(ans != -1);
  154. if(!ans) {
  155. l = mid;
  156. }
  157. else {
  158. r = mid;
  159. }
  160. }
  161. // cerr << r << '\n';
  162. if(r < n) res.insert(op[r]);
  163. cur = 0;
  164. // g[op[r]].clear();
  165. if(lol > 0) {
  166. // cerr << lol << '\n';
  167. used[lol] = 1;
  168. // g[lol].clear();
  169. }
  170. else {
  171. first = lol;
  172. }
  173. for(int i = 0; i < n; i++) {
  174. sort(all(g[i]), [&](int a, int b) {
  175. return lul[a] < lul[b];
  176. });
  177. }
  178. lol = op[r];
  179. last = 0;
  180. fill(all(op), -1);
  181. if(used[lol]) {
  182. break;
  183. }
  184. dfs(lol, -1);
  185.  
  186. // last =
  187. // used[{par[op[r]], op[r]}] = 1;
  188.  
  189. }
  190. cout << "! " << res.size() << " ";
  191. for(auto i : res) {
  192. cout << i + 1 << " ";
  193. }
  194. cout << endl;
  195. }
  196. return 0;
  197. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement