QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#401846 | #7418. Interactive Vertex | james1BadCreeper# | TL | 3ms | 10152kb | C++14 | 1.6kb | 2024-04-29 15:35:49 | 2024-04-29 15:35:50 |
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]; });
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) R = mid;
else L = mid + 1;
// cerr << L << " " << R << "\n";
}
int y = vec[R]; 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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 9520kb
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: 3ms
memory: 10152kb
input:
5 1 2 1 3 1 4 1 5 0 0 1 1
output:
? 4 1 2 3 4 5 ? 2 1 2 3 ? 1 1 4 ? 1 2 1 ! 2
result:
ok 4 queries
Test #3:
score: 0
Accepted
time: 0ms
memory: 8776kb
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: -100
Time Limit Exceeded
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 75 87 35 93 63 21 19 43 51 95 58 91 76 ? 7 ...