QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#401831 | #7418. Interactive Vertex | james1BadCreeper# | TL | 2ms | 8268kb | C++14 | 1.6kb | 2024-04-29 15:22:28 | 2024-04-29 15:22:29 |
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.size()) 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) L = mid + 1;
else R = mid;
}
int y = vec[L]; 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: 8268kb
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: -100
Time Limit Exceeded
input:
5 1 2 1 3 1 4 1 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
? 4 1 2 3 4 5 ? 2 1 2 3 ? 1 1 2 ? 1 3 1 ? 4 1 2 3 4 5 ? 2 1 2 3 ? 1 1 2 ? 1 3 1 ? 4 1 2 3 4 5 ? 2 1 2 3 ? 1 1 2 ? 1 3 1 ? 4 1 2 3 4 5 ? 2 1 2 3 ? 1 1 2 ? 1 3 1 ? 4 1 2 3 4 5 ? 2 1 2 3 ? 1 1 2 ? 1 3 1 ? 4 1 2 3 4 5 ? 2 1 2 3 ? 1 1 2 ? 1 3 1 ? 4 1 2 3 4 5 ? 2 1 2 3 ? 1 1 2 ?...