QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #755021 | #9570. Binary Tree | yld | WA | 3ms | 3644kb | C++20 | 5.3kb | 2024-11-16 16:16:40 | 2024-11-16 16:16:41 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
// #define endl '\n'
using namespace std;
int ask(int x,int y)
{
cout<<"? "<<x<<' '<<y<<endl;
int res;cin>>res;
return res;
}
void solve()
{
int n;cin>>n;
vector<int> ls(n+1),rs(n+1),fa(n+1);
vector<int> vis(n+1);
vector<int> dep(n+1),siz(n+1),now(n+1);
for(int i=1;i<=n;i++)
{
cin>>ls[i]>>rs[i];
vis[ls[i]]=1;
vis[rs[i]]=1;
}
int root;
for(int i=1;i<=n;i++)
if(!vis[i]) root=i;
function<void(int,int)> init=[&](int u,int f)
{
now[u]=now[f]+1;
fa[u]=f;
siz[u]=1;
if(ls[u])init(ls[u],u);
if(rs[u])init(rs[u],u);
dep[u]=max({now[u],dep[ls[u]],dep[rs[u]]});
siz[u]+=siz[ls[u]]+siz[rs[u]];
};
init(root,0);
// for(int i=1;i<=n;i++) cout<<dep[i]<<' ';
// cout<<endl;
// for(int i=1;i<=n;i++) cout<<siz[i]<<' ';
// cout<<endl;
// for(int i=1;i<=n;i++) cout<<now[i]<<' ';
// cout<<endl;
int times=0;
function<pair<int,int>(int)> dfs=[&](int u)->pair<int,int>
{
int maxn=now[u],res=u;
if(ls[u])
{
auto tmp=dfs(ls[u]);
if(tmp.first>maxn)
{
res=tmp.second;
maxn=tmp.first;
}
}
if(rs[u])
{
auto tmp=dfs(rs[u]);
if(tmp.first>maxn)
{
res=tmp.second;
maxn=tmp.first;
}
}
return {maxn,res};
};
int node=dfs(root).second;
int nowsiz=siz[root],nowdep=now[node]-now[root]+1;
// cout<<log2(n)<<endl;
// cout<<node<<' '<<root<<endl;
// cout<<nowdep<<endl;
// cout<<(1<<nowdep-1)-1<<endl;
while(times<(int)log2(n))
{
init(root,0);
if(abs(siz[ls[root]]-siz[rs[root]])>nowsiz/3)
{
// cout<<"================\n";
int op=ask(root,node);
if(op==0)
{
int dis=(now[node]-now[root]+2)/2-1;
int mid=node;
// cout<<dis<<endl;
for(int i=1;i<=dis;i++) mid=fa[mid];
// cout<<mid<<endl;
if(ls[fa[mid]]==mid)
{
mid=fa[mid];
nowsiz-=siz[ls[mid]];
ls[mid]=0;
}
else
{
mid=fa[mid];
nowsiz-=siz[rs[mid]];
rs[mid]=0;
}
// cout<<mid<<endl;
node=dfs(root).second;
nowdep=now[node]-now[root]+1;
}
if(op==1)
{
int dis=(now[node]-now[root]+1)/2-1;
int mid=node;
// cout<<dis<<endl;
for(int i=1;i<=dis;i++) mid=fa[mid];
// cout<<mid<<endl;
if(ls[fa[mid]]==mid)
{
mid=fa[mid];
nowsiz=siz[mid]-siz[ls[mid]];
ls[mid]=0;
}
else
{
mid=fa[mid];
nowsiz=siz[mid]-siz[rs[mid]];
rs[mid]=0;
}
// cout<<mid<<endl;
root=mid;
node=dfs(root).second;
nowdep=now[node]-now[root]+1;
}
if(op==2)
{
int dis=(now[node]-now[root]+1)/2-1;
int mid=node;
for(int i=1;i<=dis;i++) mid=fa[mid];
nowsiz=siz[mid];
root=mid;
nowdep=now[node]-now[root]+1;
}
}
else
{
if(ls[root] && rs[root])
{
// cout<<"==========\n";
int op=ask(ls[root],rs[root]);
if(op==0)
{
root=ls[root];
nowsiz=siz[root];
node=dfs(root).second;
nowdep=now[node]-now[root]+1;
}
if(op==1)
{
cout<<"! "<<root<<endl;
return;
}
if(op==2)
{
root=rs[root];
nowsiz=siz[root];
node=dfs(root).second;
nowdep=now[node]-now[root]+1;
}
}
else if(ls[root] || rs[root])
{
int son=(ls[root]?ls[root]:rs[root]);
int op=ask(root,son);
if(op==0)
{
cout<<"! "<<root<<endl;
return;
}
if(op==2)
{
root=son;
nowsiz=siz[son];
node=dfs(root).second;
nowdep=now[node]-now[root]+1;
}
}
else {cout<<"! "<<root<<endl;return;}
}
times++;
}
cout<<"! "<<root<<endl;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
input:
2 5 0 0 1 5 2 4 0 0 0 0 1 0 2 0 2 0 0 2
output:
? 3 1 ? 2 5 ! 2 ? 1 2 ! 2
result:
ok OK (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3644kb
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 2 0 8 5 8 0 0 1 7 0 0 0 0 4 2 0 0 6 0 0 0 2 5 4 5 3 1 0 0 0 0 0 0 0 0 8 0 0 0 0 5 6 0 0 1 4 2 0 3 8 0 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 0 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 ...
output:
? 1 3 ? 1 7 ? 6 7 ! 6 ? 5 1 ? 7 8 ? 8 6 ! 8 ? 3 4 ? 1 7 ? 1 5 ! 5 ? 2 4 ? 2 3 ! 2 ? 7 1 ? 7 2 ? 3 8 ! 3 ? 5 1 ? 1 3 ! 1 ? 1 3 ? 1 2 ! 2 ? 2 3 ! 1 ? 1 2 ! 2 ? 2 3 ! 3 ? 1 4 ? 1 10 ? 2 8 ! 1 ? 1 2 ! 1 ? 3 7 ? 7 6 ? 7 1 ! 1 ? 3 10 ? 10 6 ? 6 2 ! 6 ? 8 2 ? 8 6 ? 3 5 ! 5 ? 2 1 ! 1 ? 7 2 ? 7 1 ! 1 ? 6 2 ?...
result:
wrong answer There are 2 candidates. (test case 21)