QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#732900	#9570. Binary Tree	ucup-team4479^#	RE	1ms	3844kb	C++23	2.3kb	2024-11-10 16:21:40	2024-11-10 16:21:41

Judging History

你现在查看的是最新测评结果

[2024-11-10 16:21:41]
评测

测评结果：RE
用时：1ms
内存：3844kb

查看

[2024-11-10 16:21:40]
提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=200005;
int n;
vector<int>G[N];
int query(int x,int y)
{
    cout<<"? "<<x<<" "<<y<<endl;
    int t;
    cin>>t;
    return t;
}
void submit(int x)
{
    cout<<"! "<<x<<endl;
    return;
}
int siz[N];
int mx[N];
int rt,tot;
bool vis[N];
void findroot(int u,int father)
{
    siz[u]=1;
    mx[u]=0;
    for(int v:G[u])
    {
        if(v==father) continue;
        if(vis[v]) continue;
        findroot(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }
    mx[u]=max(mx[u],tot-siz[u]);
    if(rt==0||mx[u]<mx[rt]) rt=u;
    return;
}
int p;
void dfs(int u)
{
    vector<int>son;
    for(int v:G[u])
    {
        if(vis[v]) continue;
        son.emplace_back(v);
    }
    if((int)son.size()==0)
    {
        p=u;
        return;
    }
    else if((int)son.size()==1)
    {
        int t=query(u,son[0]);
        if(t==0) p=u;
        else if(t==2)
        {
            vis[u]=true;
            tot=siz[son[0]],rt=0;
            findroot(son[0],0);
            findroot(rt,0);
            dfs(rt);
        }
    }
    else
    {
        int t=query(son[0],son[1]);
        if(t==0)
        {
            vis[u]=true;
            tot=siz[son[0]],rt=0;
            findroot(son[0],0);
            findroot(rt,0);
            dfs(rt);
        }
        else if(t==2)
        {
            vis[u]=true;
            tot=siz[son[1]],rt=0;
            findroot(son[1],0);
            findroot(rt,0);
            dfs(rt);
        }
        else
        {
            vis[son[0]]=vis[son[1]]=true;
            tot-=siz[son[0]]+siz[son[1]],rt=0;
            findroot(u,0);
            findroot(rt,0);
            dfs(rt);
        }
    }
    return;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        G[i].clear(),vis[i]=false;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x) G[i].emplace_back(x),G[x].emplace_back(i);
        if(y) G[i].emplace_back(y),G[y].emplace_back(i); 
    }
    tot=n,rt=0;
    p=0;
    findroot(1,0);
    findroot(rt,0);
    dfs(rt);
    submit(p);
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    // cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3844kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: