QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #716142 | #9570. Binary Tree | Sulfox# | WA | 11ms | 3844kb | C++20 | 3.2kb | 2024-11-06 14:30:35 | 2024-11-06 14:30:36 |
Judging History
answer
#include <bits/stdc++.h>
const int N = 1e5 + 5;
int n, rt, cr, siz[N], hs[N], son[N][2], ft[N];
bool isr[N];
void find1(int u) {
siz[u] = 1;
hs[u] = 0;
if (son[u][0]) {
ft[son[u][0]] = u;
find1(son[u][0]);
siz[u] += siz[son[u][0]];
hs[u] = std::max(hs[u], siz[son[u][0]]);
}
if (son[u][1]) {
ft[son[u][1]] = u;
find1(son[u][1]);
siz[u] += siz[son[u][1]];
hs[u] = std::max(hs[u], siz[son[u][1]]);
}
}
void find2(int u) {
hs[u] = std::max(hs[u], siz[rt] - siz[u]);
if (son[u][0]) {
find2(son[u][0]);
}
if (son[u][1]) {
find2(son[u][1]);
}
if (!son[u][0] && !son[u][1]) return;
if (u == rt && !son[u][0]) return;
if (u == rt && !son[u][1]) return;
if (cr == -1 || hs[cr] > hs[u]) cr = u;
}
void run() {
scanf("%d", &n);
for (int u = 1; u <= n; u++)
isr[u] = true;
for (int u = 1; u <= n; u++) {
scanf("%d%d", &son[u][0], &son[u][1]);
isr[son[u][0]] = isr[son[u][1]] = false;
}
for (int u = 1; u <= n; u++)
if (isr[u])
rt = u;
for (; ; ) {
cr = -1;
find1(rt);
find2(rt);
if (siz[rt] == 1) {
printf("! %d\n", rt);
fflush(stdout);
break;
}
int u = cr;
if (u == -1) {
u = rt;
printf("? %d %d\n", u, std::max(son[u][0], son[u][1]));
fflush(stdout);
int res;
scanf("%d", &res);
if (res == 0) {
son[u][0] = son[u][1] = 0;
} else {
rt = std::max(son[u][0], son[u][1]);
}
} else if (!son[u][0]) {
printf("? %d %d\n", ft[u], son[u][1]);
fflush(stdout);
int res;
scanf("%d", &res);
if (res == 0) {
if (son[ft[u]][0] == u)
son[ft[u]][0] = 0;
else
son[ft[u]][1] = 0;
} else if (res == 1) {
rt = u;
son[u][1] = 0;
} else {
rt = son[u][1];
}
} else if (!son[u][1]) {
printf("? %d %d\n", ft[u], son[u][0]);
fflush(stdout);
int res;
scanf("%d", &res);
if (res == 0) {
if (son[ft[u]][0] == u)
son[ft[u]][0] = 0;
else
son[ft[u]][1] = 0;
} else if (res == 1) {
rt = u;
son[u][0] = 0;
} else {
rt = son[u][0];
}
} else {
printf("? %d %d\n", son[u][0], son[u][1]);
fflush(stdout);
int res;
scanf("%d", &res);
if (res == 0) {
rt = son[u][0];
} else if (res == 1) {
son[u][0] = son[u][1] = 0;
} else {
rt = son[u][1];
}
}
}
}
int main() {
int T;
scanf("%d", &T);
for (; T; T--) run();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
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 ? 1 2 ! 2
result:
ok OK (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 11ms
memory: 3844kb
input:
5555 8 2 0 8 6 0 0 3 0 0 0 7 0 0 0 5 4 1 2 0 8 0 0 1 4 2 0 0 0 7 8 0 0 3 0 6 0 0 0 2 8 5 8 0 0 1 7 0 0 0 0 4 2 0 0 6 0 0 0 0 5 4 5 3 1 0 0 0 0 0 0 1 1 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 2 0 5 5 0 0 0 0 0 3 0 2 4 1 2 3 3 0 1 0 0 0 1 2 2 0 0 0 2 3 2 3 0 0 0 0 2 10 2 8 9 7 0 0 ...
output:
? 5 4 ? 8 6 ? 6 7 ! 6 ? 7 2 ? 5 6 ? 5 7 ! 7 ? 1 6 ? 3 5 ? 3 7 ! 3 ? 4 5 ? 3 1 ! 2 ? 5 6 ? 1 4 ! 1 ? 5 1 ? 1 3 ! 1 ? 2 4 ? 1 5 ! 5 ? 2 3 ! 1 ? 1 2 ! 2 ? 2 3 ! 3 ? 6 5 ? 9 7 ? 2 8 ! 1 ? 1 2 ! 1 ? 5 9 ? 4 8 ? 5 3 ! 3 ? 5 8 ? 7 1 ? 7 9 ! 7 ? 3 4 ? 1 7 ? 8 2 ! 2 ? 2 1 ! 1 ? 3 6 ? 5 1 ? 7 4
result:
wrong answer Too many queries (test case 17)