QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #734071 | #9570. Binary Tree | xly_tyty# | RE | 0ms | 5688kb | C++23 | 2.2kb | 2024-11-10 23:39:05 | 2024-11-10 23:39:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+10;
int st[N],root,siz[N];
int n,m,k,x,w;
vector<int>p[N];
int query(int a,int b)
{
cout<<'?'<<' '<<a<<' '<<b<<endl;
int x;cin>>x;
return x;
}
pii ans;
int mx,ty=0;
void dfs(int u,int fa)
{
siz[u]=1;
int l=0,r=0;
for(int x:p[u])
{
if(st[x]||x==fa)continue;
if(l==0)l=x;
else if(r==0)r=x;
dfs(x,u);
siz[u]+=siz[x];
}
if(l!=0&&r==0)
{
int res=min(siz[l],n-siz[l]);
if(res>mx)
{
mx=res;
ans={u,l};
ty=0;
}
}
else if(l!=0&&r!=0)
{
int res=max({siz[l],siz[r],n-siz[l]-siz[r]});
res=n-res;
if(res>mx)
{
mx=res;
ans={l,r};
ty=u;
}
}
}
void solve()
{
cin>>n;
m=n;
for(int i=0;i<=n+10;i++)p[i].clear(),st[i]=0;
for(int i=1;i<=n;i++)
{
int l,r;cin>>l>>r;
if(l)p[i].push_back(l),p[l].push_back(i);
if(r)p[i].push_back(r),p[r].push_back(i);
}
root=1;
int ct=2;
while(1)
{
mx=0;
ty=0;
dfs(root,0);
int l=ans.first,r=ans.second;
int cnt = 0;
//int t=0;
if(n==3)
{
int ll=0,rr=0;
for(int x:p[root])
{
if(st[x])continue;
cnt++;
if(ll==0)ll=x;
else if(rr==0)rr=x;
}
//cout<<root<<' '<<ll<<' '<<rr<<endl;
if(cnt!=2)
{
root=ll;
continue;
}
}
int x=query(l,r);
ct*=2;
if(n==2)
{
if(!x)cout<<'!'<<' '<<l<<endl;
else cout<<'!'<<' '<<r<<endl;
return;
}
else if(n==3)
{
if(!x)cout<<'!'<<' '<<l<<endl;
else if(x==1)cout<<'!'<<' '<<root<<endl;
else cout<<'!'<<' '<<r<<endl;
return;
}
//cout<<n<<endl;
if(!ty)
{
if(!x)st[ans.second]=1,n-=siz[ans.second],root=ans.first;
else st[ans.first]=1,n=siz[ans.second],root=ans.second;
//cout<<ans.second<<' '<<siz[ans.second]<<endl;
}
else{
if(!x)st[ty]=1,st[r]=1,n=siz[ans.first],root=ans.first;
else if(x==1)st[l]=1,st[r]=1,n-=siz[ans.first]+siz[ans.second],root=ty;
else st[ty]=1,st[l]=1,n=siz[ans.second],root=ans.second;
}
if(n==1)
{
cout<<'!'<<' '<<root<<endl;return;
}
if(ct>m)
{
cout<<"CAONIMA"<<endl;return;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;cin>>t;
while(t--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5688kb
input:
2 5 0 0 1 5 2 4 0 0 0 0 2 0 2 0 2 0 0 2
output:
? 5 3 ? 3 4 ! 3 ? 1 2 ! 2
result:
ok OK (2 test cases)
Test #2:
score: -100
Runtime Error
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 0 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 1 1 0 5 3 0 5 1 0 0 0 0 4 0 0 1 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 ...
output:
? 8 6 ? 5 4 ? 4 3 ! 4 ? 3 7 ? 5 8 ? 5 7 ! 7 ? 5 8 ? 4 2 ? 6 8 ! 6 ? 4 5 ? 3 1 ! 3 ? 6 7 ? 1 4 ? 5 3 ! 5 ? 2 5 ? 3 2 ! 1 ? 2 4 ? 5 1 ! 1 ? 3 2 ! 1 ? 1 2 ! 2 ? 2 3 ! 3 ? 9 7 ? 4 3 ? 6 5 ! 7 ? 1 2 ! 1 ? 7 5 ? 2 1 ? 2 6 ! 6 ? 5 10 ? 7 1 ? 7 9 ! 9 ? 3 4 ? 1 7 ? 8 2 ! 2 ? 1 2 ! 2 ? 3 6 ? 1 7 CAONIMA