QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#401851 | #7418. Interactive Vertex | james1BadCreeper# | WA | 3ms | 10116kb | C++14 | 1.7kb | 2024-04-29 15:44:04 | 2024-04-29 15:44:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, ans = -1;
vector<int> G[N];
bool vis[N];
int sz[N], mxs[N], rt;
int ask(int x, vector<int> v) {
cout << "? " << v.size() << ' ' << x << ' ';
for (int i : v) cout << i << ' ';
cout << endl; cin >> x;
return x;
}
void froot(int x, int fa, int tot) {
sz[x] = 1; mxs[x] = 0;
for (int y : G[x]) if (y != fa && !vis[y])
froot(y, x, tot), sz[x] += sz[y], mxs[x] = max(mxs[x], sz[y]);
mxs[x] = max(mxs[x], tot - sz[x]);
if (mxs[rt] > mxs[x]) rt = x;
}
void solve(int x) {
if (ans != -1) return;
vector<int> vec;
for (int y : G[x]) if (!vis[y]) vec.emplace_back(y);
if (vec.empty()) return ans = x, void();
if (ask(x, vec) == 1) return ans = x, void();
// sort(vec.begin(), vec.end(), [&](int u, int v){ return sz[u] < sz[v]; });
vis[x] = 1;
int L = 0, R = vec.size() - 1;
while (L < R) {
int mid = L + R >> 1; // 3 4
vector<int> now;
for (int i = L; i <= mid; ++i) now.emplace_back(vec[i]);
if (ask(x, now) == 1) L = mid + 1;
else R = mid;
// cerr << L << " " << R << endl;
}
int y = vec[L];
// cerr << "FOUND " << y << endl;
int all = sz[y];
rt = 0; froot(y, 0, all); froot(rt, 0, all);
solve(rt);
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
G[u].emplace_back(v); G[v].emplace_back(u);
}
mxs[0] = 1e9;
int all = n;
froot(1, 0, all); froot(rt, 0, all);
solve(rt);
cout << "! " << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10116kb
input:
5 1 2 1 3 1 4 1 5 1
output:
? 4 1 2 3 4 5 ! 1
result:
ok 1 queries
Test #2:
score: 0
Accepted
time: 0ms
memory: 8312kb
input:
5 1 2 1 3 1 4 1 5 0 0 0
output:
? 4 1 2 3 4 5 ? 2 1 2 3 ? 1 1 2 ! 2
result:
ok 3 queries
Test #3:
score: 0
Accepted
time: 0ms
memory: 8536kb
input:
7 1 2 2 3 3 4 4 5 3 6 6 7 1
output:
? 3 3 2 4 6 ! 3
result:
ok 1 queries
Test #4:
score: 0
Accepted
time: 2ms
memory: 8236kb
input:
100 75 98 98 87 35 98 98 93 98 63 83 25 98 21 97 25 19 98 8 25 43 98 28 94 92 28 51 98 6 28 95 98 58 98 12 28 4 42 9 28 30 25 91 98 28 77 98 76 24 42 28 82 14 25 28 32 98 1 81 98 42 50 98 71 98 26 20 98 80 39 28 23 70 28 88 25 69 28 28 99 41 98 98 55 29 98 61 28 27 28 11 25 98 84 34 28 98 100 36 98 ...
output:
? 51 98 75 87 35 93 63 21 19 43 51 95 58 91 76 1 81 71 26 20 41 55 29 84 100 36 79 15 85 56 45 48 52 62 28 78 46 96 64 59 18 2 89 68 90 65 31 66 13 54 17 40 73 ? 26 98 75 87 35 93 63 21 19 43 51 95 58 91 76 1 81 71 26 20 41 55 29 84 100 36 79 15 ? 13 98 85 56 45 48 52 62 28 78 46 96 64 59 18 ? 7 ...
result:
ok 22 queries
Test #5:
score: 0
Accepted
time: 3ms
memory: 9304kb
input:
203 139 160 172 95 170 39 106 39 3 95 6 39 130 16 148 65 62 160 109 39 39 69 23 16 95 84 39 11 95 37 36 39 95 103 60 39 94 39 39 35 39 123 138 39 199 39 5 16 65 160 142 16 77 39 135 39 97 39 39 72 95 92 39 44 65 200 65 129 39 152 39 176 16 86 16 95 39 143 198 39 95 90 39 17 197 39 89 16 95 189 16 47...
output:
? 102 39 170 106 6 109 69 11 36 60 94 35 123 138 199 77 135 97 72 44 152 176 143 198 17 197 178 127 78 102 180 157 191 38 91 192 114 185 25 122 113 28 24 131 64 147 54 46 184 43 95 57 196 169 79 161 175 203 51 12 154 136 73 190 158 121 179 159 10 19 112 58 171 59 120 63 98 88 66 68 188 145 124 83 12...
result:
ok 30 queries
Test #6:
score: -100
Wrong Answer
time: 3ms
memory: 8436kb
input:
406 77 136 231 136 177 130 390 136 342 127 136 128 254 136 136 32 136 295 102 342 137 214 342 3 120 136 43 406 406 55 72 371 136 183 136 97 331 72 342 397 108 136 136 315 136 105 72 316 136 328 136 111 214 327 335 130 136 203 72 110 406 355 136 336 107 136 136 333 136 330 339 136 84 406 136 152 201 ...
output:
? 204 136 77 231 390 128 254 32 295 120 183 97 108 315 105 328 111 203 336 107 333 330 339 152 217 306 236 116 370 26 133 129 95 22 374 318 352 1 302 237 279 233 69 202 76 88 141 200 191 194 266 234 263 299 239 192 157 53 325 240 262 44 362 210 391 280 142 50 367 75 358 90 40 395 228 180 301 184 265...
result:
wrong answer too many queries: 37 queries, bigger than 36