QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #729865 | #9570. Binary Tree | ucup-team1264# | WA | 3ms | 1632kb | C++20 | 2.7kb | 2024-11-09 17:58:01 | 2024-11-09 17:58:05 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
int ask(int x, int y) {
printf("? %d %d\n", x, y);
fflush(stdout);
int tmp;
scanf("%d", &tmp);
return tmp;
}
int T, n, root, ls[100005], rs[100005], fa[100005], siz[100005];
int mid;
void dfs1(int x) {
siz[x] = 1;
if (ls[x]) {
dfs1(ls[x]);
siz[x] += siz[ls[x]];
}
if (rs[x]) {
dfs1(rs[x]);
siz[x] += siz[rs[x]];
}
}
void dfs2(int x) {
if (ls[x]) dfs2(ls[x]);
if (rs[x]) dfs2(rs[x]);
if (mid == -1 && siz[x] * 2 >= siz[root]) mid = x;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1;i <= n;i++) fa[i] = ls[i] = rs[i] = siz[i] = 0;
for (int i = 1;i <= n;i++) {
scanf("%d%d", &ls[i], &rs[i]);
if (ls[i]) fa[ls[i]] = i;
if (rs[i]) fa[rs[i]] = i;
}
for (int i = 1;i <= n;i++) if (!fa[i]) root = i;
while (1) {
mid = -1;
dfs1(root);
dfs2(root);
if (siz[root] == 1) break;
// printf("%d %d\n", root, mid);
if (!ls[mid] && !rs[mid]) {
int res = ask(fa[mid], mid);
root = (res == 0 ? fa[mid] : mid);
break;
}
else if (!ls[mid]) {
int res = ask(fa[mid], rs[mid]);
if (res == 0) {
if (ls[fa[mid]] == mid) ls[fa[mid]] = 0;
else rs[fa[mid]] = 0;
}
if (res == 1) {
root = mid;
break;
}
if (res == 2) {
root = rs[mid];
}
}
else if (!rs[mid]) {
int res = ask(fa[mid], ls[mid]);
if (res == 0) {
if (ls[fa[mid]] == mid) ls[fa[mid]] = 0;
else rs[fa[mid]] = 0;
}
if (res == 1) {
root = mid;
break;
}
if (res == 2) {
root = ls[mid];
}
}
else {
int res = ask(ls[mid], rs[mid]);
if (res == 0) {
root = ls[mid];
}
if (res == 1) {
ls[mid] = 0;
rs[mid] = 0;
}
if (res == 2) {
root = rs[mid];
}
}
}
printf("! %d\n", root);
fflush(stdout);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1616kb
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: 3ms
memory: 1632kb
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)