QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #783560 | #9570. Binary Tree | Dixiky_215 | WA | 1ms | 5708kb | C++20 | 5.1kb | 2024-11-26 10:37:42 | 2024-11-26 10:37:46 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+7;
int t,n;
int siz[MAXN],id[MAXN],tot=0;
int l_son[MAXN],r_son[MAXN],fa[MAXN];
int maxl[MAXN],rot,du[MAXN],now_num=0;
bool vis[MAXN];
void dfs(int x)
{
siz[x]=1;
id[++tot]=x;maxl[x]=0;
if(l_son[x])
{
dfs(l_son[x]);
siz[x]+=siz[l_son[x]];
maxl[x]=max(maxl[x],siz[l_son[x]]);
}
if(r_son[x])
{
dfs(r_son[x]);
siz[x]+=siz[r_son[x]];
maxl[x]=max(maxl[x],siz[r_son[x]]);
}
maxl[x]=max(maxl[x],now_num-siz[x]);
return;
}
int ask(int x,int y)
{
int sss;
cout<<"? "<<x<<" "<<y<<endl;
cin>>sss;
return sss;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>l_son[i]>>r_son[i];
if(l_son[i]) du[l_son[i]]++,fa[l_son[i]]=i;
if(r_son[i]) du[r_son[i]]++,fa[r_son[i]]=i;
}
for(int i=1;i<=n;i++) if(!du[i]) {rot=i;break;}
now_num=n;
while(1)
{
tot=0;
dfs(rot);
if(tot==1)
{
cout<<"! "<<id[1]<<endl;
break;
}
int minl=1e9,min_id;
for(int i=1;i<=tot;i++)
{
int x=id[i];
if(minl>maxl[x])
{
minl=maxl[x];
min_id=x;
}
}
int x=min_id;
if(fa[x]==0)
{
if(l_son[x]&&r_son[x])
{
int sss=ask(l_son[x],r_son[x]);
if(sss==0)
{
fa[l_son[x]]=0;
rot=l_son[x];
now_num=siz[rot];
}
else if(sss==2)
{
fa[r_son[x]]=0;
rot=r_son[x];
now_num=siz[rot];
}
else
{
cout<<"! "<<x<<endl;
break;
}
}
else if(l_son[x])
{
int sss=ask(l_son[x],x);
if(sss==0) cout<<"! "<<l_son[x]<<endl;
else cout<<"! "<<x<<endl;
break;
}
else if(r_son[x])
{
int sss=ask(r_son[x],x);
if(sss==0) cout<<"! "<<r_son[x]<<endl;
else cout<<"! "<<x<<endl;
break;
}
}
else
{
if(l_son[x]&&r_son[x])
{
int sss=ask(l_son[x],r_son[x]);
if(sss==0)
{
fa[l_son[x]]=0;
rot=l_son[x];
now_num=siz[rot];
}
else if(sss==2)
{
fa[r_son[x]]=0;
rot=r_son[x];
now_num=siz[rot];
}
else
{
now_num-=siz[l_son[x]]+siz[r_son[x]];
l_son[x]=0;r_son[x]=0;
}
}
else if(l_son[x])
{
int sss=ask(l_son[x],x);
if(sss==0)
{
fa[l_son[x]]=0;
rot=l_son[x];
now_num=siz[rot];
}
else if(sss==2)
{
now_num-=siz[l_son[x]];
l_son[x]=0;
}
}
else if(r_son[x])
{
int sss=ask(r_son[x],x);
if(sss==0)
{
fa[r_son[x]]=0;
rot=r_son[x];
now_num=siz[rot];
}
else if(sss==2)
{
now_num-=siz[r_son[x]];
r_son[x]=0;
}
}
else
{
int sss=ask(x,fa[x]);
if(sss==0) cout<<"! "<<x<<endl;
else cout<<"! "<<fa[x]<<endl;
break;
}
}
for(int i=0;i<=tot;i++) siz[id[i]]=0,maxl[id[i]]=0;
}
for(int i=0;i<=n;i++)
{
siz[i]=fa[i]=maxl[i]=0;
l_son[i]=r_son[i]=0;
vis[i]=0;
du[i]=0;
}
}
return 0;
}
/*
1
5
0 0
1 5
2 4
0 0
0 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5648kb
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: 5708kb
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 2 2 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 0 8 0 0 0 0 5 6 0 0 1 4 2 0 3 8 0 0 0 1 5 3 0 5 1 0 0 0 0 4 0 0 2 5 5 0 0 0 0 0 3 0 2 4 2 0 3 3 0 1 0 0 0 2
output:
? 8 6 ? 5 4 ? 3 4 ! 3 ? 3 7 ? 7 8 ? 6 8 ! 8 ? 5 8 ? 4 2 ? 6 8 ! 6 ? 4 5 ? 3 1 ! 3 ? 5 6 ? 1 4 ! 5 ? 5 1 ? 4 5 ! 5 ? 2 4 ? 3 4 ! 3 ? 3 1 ? 1 2
result:
wrong answer Too many queries (test case 8)