QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #769296 | #9570. Binary Tree | kisaki | WA | 1ms | 3792kb | C++14 | 2.2kb | 2024-11-21 17:00:09 | 2024-11-21 17:00:09 |
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;
void minn(int p,int min){
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]])<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]]);
pos=p;
}
if(l[p])minn(l[p],min);
if(r[p])minn(r[p],min);
}
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){
minn(root,INF);
if(l[pos]&&r[pos]){//d=2 or 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]){
std::cout<<"? "<<l[pos]<<" "<<fa[pos]<<"\n";std::cout.flush();
scanf("%d",&st);
if(st==0)root=l[pos],fa[root]=0;
else l[pos]=r[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 l[pos]=r[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
7
2 0
3 0
4 0
5 0
6 0
7 0
0 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3648kb
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: 3792kb
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
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
result:
wrong answer Too many queries (test case 8)