QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #769356 | #9570. Binary Tree | kisaki | WA | 2ms | 3848kb | C++14 | 2.7kb | 2024-11-21 17:16:55 | 2024-11-21 17:16:55 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define N 100010
typedef long long ll;
int t,n,root;
int l[N],r[N],fa[N],size[N],cnt;
void dfs_size(int p){
size[p]=1;
if(l[p])dfs_size(l[p]),size[p]+=size[l[p]];
if(r[p])dfs_size(r[p]),size[p]+=size[r[p]];
}
int max(int a,int b,int c){
return std::max(a,std::max(b,c));
}
int pos,min;
void minn(int p){
if(fa[p]&&l[p]&&r[p]){
if(max(size[l[p]],size[r[p]],size[root]-size[l[p]]-size[r[p]])<=min){
min=max(size[l[p]],size[r[p]],size[root]-size[l[p]]-size[r[p]]);
pos=p;
}
}
else if(max(size[l[p]],size[r[p]],size[root]-size[l[p]]-size[r[p]]-1)<min&&((fa[p]&&l[p])||(fa[p]&&r[p])||(l[p]&&r[p]))){
min=max(size[l[p]],size[r[p]],size[root]-size[l[p]]-size[r[p]]-1);
pos=p;
}
if(l[p])minn(l[p]);
if(r[p])minn(r[p]);
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++)size[i]=0,fa[i]=0;
for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]),fa[l[i]]=fa[r[i]]=i;
for(int i=1;i<=n;i++){
if(!fa[i]){
root=i;
break;
}
}
int st;
dfs_size(root);
while(size[root]>2){
min=INF;
minn(root);
if(l[pos]&&r[pos]&&fa[pos]){//d=3
std::cout<<"? "<<l[pos]<<" "<<r[pos]<<"\n";std::cout.flush();
scanf("%d",&st);
if(st==0)root=l[pos],fa[root]=0;
else if(st==2)root=r[pos],fa[root]=0;
else l[pos]=r[pos]=0;
}
else if(l[pos]&&r[pos]){
std::cout<<"? "<<l[pos]<<" "<<r[pos]<<"\n";std::cout.flush();
scanf("%d",&st);
if(st==0)root=l[pos],fa[root]=0;
else if(st==2)root=r[pos],fa[root]=0;
else l[pos]=r[pos]=0;
}
else if(l[pos]){
std::cout<<"? "<<l[pos]<<" "<<fa[pos]<<"\n";std::cout.flush();
scanf("%d",&st);
if(st==0)root=l[pos],fa[root]=0;
else if(st==1)root=pos,l[pos]=r[pos]=fa[pos]=0;
else {
if(r[fa[pos]]==pos)r[fa[pos]]=0;
else l[fa[pos]]=0;
}
}
else if(r[pos]){
std::cout<<"? "<<r[pos]<<" "<<fa[pos]<<"\n";std::cout.flush();
scanf("%d",&st);
if(st==0)root=r[pos],fa[root]=0;
else if(st==1)root=pos,l[pos]=r[pos]=fa[pos]=0;
else{
if(r[fa[pos]]==pos)r[fa[pos]]=0;
else l[fa[pos]]=0;
}
}
dfs_size(root);
}
if(size[root]==1){
std::cout<<"! "<<root<<"\n";std::cout.flush();
}
else{
int qwq=std::max(l[root],r[root]);
std::cout<<"? "<<qwq<<" "<<root<<"\n";std::cout.flush();
scanf("%d",&st);
if(st==0){
std::cout<<"! "<<qwq<<"\n";std::cout.flush();
}
else{
std::cout<<"! "<<root<<"\n";std::cout.flush();
}
}
}
return 0;
}
/*
1
6
2 0
3 4
5 0
0 6
0 0
0 0
7
2 0
3 0
4 0
5 0
6 0
7 0
0 0
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3848kb
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: 2ms
memory: 3716kb
input:
5555 8 2 0 8 6 0 0 3 0 0 0 7 0 0 0 5 4 0 2 0 8 0 0 1 4 2 0 0 0 7 8 0 0 3 0 6 0 0 1 2 8 5 8 0 0 1 7 0 0 0 0 4 2 0 0 6 0 2 1 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:
? 8 6 ? 5 4 ? 3 4 ! 3 ? 3 5 ? 1 4 ? 2 3 ! 3 ? 5 8 ? 4 2 ? 6 8 ! 6 ? 4 5 ? 3 1 ! 2 ? 5 6 ? 1 4 ! 1 ? 5 1 ? 3 1 ! 3 ? 2 4 ? 5 1 ! 1 ? 3 2 ! 1 ? 2 1 ! 1 ? 2 3 ! 3 ? 9 7 ? 4 3 ? 6 5 ! 7 ? 2 1 ! 2 ? 9 5 ? 2 1 ? 6 2 ! 2 ? 3 10 ? 6 2 ? 4 10 ! 4 ? 3 4 ? 1 7 ? 8 2 ! 2 ? 1 2 ! 2 ? 3 6 ? 5 1 ? 4 7
result:
wrong answer Too many queries (test case 17)