QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#727841 | #9570. Binary Tree | ucup-team3931# | WA | 3ms | 11344kb | C++14 | 2.4kb | 2024-11-09 13:57:10 | 2024-11-09 13:57:12 |
Judging History
answer
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
bool Mbe;
const int N = 2e5 + 5;
int n, rt, sum;
int vs[N], sz[N], mx[N], vis[N];
vector<int> G[N];
void ans(int u) {
printf("! %d\n", u);
fflush(stdout);
}
int qry(int u, int v) {
printf("? %d %d\n", u, v);
fflush(stdout);
int d; scanf("%d", &d);
return d;
}
void dfs(int u, int f) {
sz[u] = 1, mx[u] = 0;
for (int v : G[u]) {
if (v == f || vs[v]) {
continue;
}
dfs(v, u);
mx[u] = max(mx[u], sz[v]);
sz[u] += sz[v];
}
mx[u] = max(mx[u], sum - sz[u]);
if (!rt || mx[u] < mx[rt]) {
rt = u;
}
}
void dfz(int u) {
queue<int> q;
q.push(u), sum = rt = 0;
vector<int> nd;
while (!q.empty()) {
int u = q.front();
q.pop(), sum++, nd.eb(u), vis[u] = 1;
for (int v : G[u]) {
if (vs[v] || vis[v]) {
continue;
}
q.push(v);
}
}
for (int u : nd) {
vis[u] = 0;
}
if (sum == 1) {
ans(u);
return;
}
dfs(u, 0);
vector<int> p;
for (int v : G[rt]) {
if (!vs[v]) {
p.eb(v);
}
}
assert((int)p.size() != 0);
if (p.size() == 1) {
if (qry(rt, p[0]) == 0) {
ans(rt);
} else {
ans(p[0]);
}
return;
} else if (p.size() == 2) {
int d = qry(p[0], p[1]);
if (d == 0) {
vs[rt] = 1;
dfz(p[0]);
} else if (d == 1) {
ans(rt);
return;
} else {
vs[rt] = 1;
dfz(p[1]);
}
} else {
int d = qry(p[0], p[1]);
if (d == 0) {
vs[rt] = 1;
dfz(p[0]);
} else if (d == 1) {
vs[p[0]] = vs[p[1]] = 1;
dfz(rt);
} else {
vs[rt] = 1;
dfz(p[1]);
}
}
}
void solve() {
scanf("%d", &n);
F (i, 1, n) {
G[i].clear();
vs[i] = 0;
}
F (i, 1, n) {
int x, y;
cin >> x >> y;
if (x) {
G[x].eb(i);
G[i].eb(x);
}
if (y) {
G[y].eb(i);
G[i].eb(y);
}
}
dfz(1);
}
bool Med;
int main() {
// FIO("");
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
int T = 1;
scanf("%d", &T);
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 10168kb
input:
2 5 0 0 1 5 2 4 0 0 0 0 1 1 2 0 2 0 0 2
output:
? 1 5 ? 2 4 ! 3 ? 2 1 ! 1
result:
ok OK (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 11344kb
input:
5555 8 2 0 8 6 0 0 3 0 0 0 7 0 0 0 5 4 0 0 2 8 0 0 1 4 2 0 0 0 7 8 0 0 3 0 6 0 2 1 0 8 5 8 0 0 1 7 0 0 0 0 4 2 0 0 6 0 0 0 2 5 4 5 3 1 0 0 0 0 0 0 1 2 8 0 0 0 0 5 6 0 0 1 4 2 0 3 8 0 0 0 0 5 3 0 5 1 0 0 0 0 4 0 0 2 5 5 0 0 0 0 0 3 0 2 4 1 0 3 3 0 1 0 0 0 2 2 2 0 0 0 0 3 2 3 0 0 0 0 2 10 2 8 9 7 0 0 ...
output:
? 2 5 ? 2 7 ? 1 2 ! 2 ? 5 3 ? 1 4 ? 3 2 ! 3 ? 1 6 ? 1 7 ? 5 1 ! 1 ? 4 5 ? 3 1 ! 1 ? 5 6 ? 1 4 ! 1 ? 5 1 ? 4 5 ! 5 ? 1 2 ? 3 5 ! 3 ? 3 2 ! 2 ? 2 1 ! 2 ? 2 3 ! 3 ? 2 6 ? 1 9 ? 10 9 ! 9 ? 2 1 ! 2 ? 5 9 ? 4 8 ? 5 3 ! 5 ? 5 8 ? 7 1 ? 5 3 ! 5 ? 3 4 ? 1 7 ? 8 2 ! 2 ? 2 1 ! 1 ? 4 3 ? 1 7 ! 7 ? 4 9 ? 2 3 ? 4...
result:
wrong answer Too many queries (test case 90)