QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#730103	#9570. Binary Tree	ucup-team4074^#	RE	0ms	8884kb	C++17	2.6kb	2024-11-09 18:43:11	2024-11-09 18:43:12

Judging History

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

[2024-11-09 18:43:12]
评测

测评结果：RE
用时：0ms
内存：8884kb

查看

[2024-11-09 18:43:11]
提交

answer


#include<bits/stdc++.h>

#define int long long
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

void solve();

signed main() {
   // fast
    int t = 1;
    cin >> t;
    while (t--) solve();
}

const int N = 2e5 + 10;
const int maxn=200010;
vector<int>e[maxn];
bool v[maxn];
int rt=0,rtmx=2e18,s[maxn],sum;
int n;
int dfs(int x,int fa)
{
    int sum=1;
    for(int i=0;i<e[x].size();i++)
    {
        if(!v[e[x][i]]||e[x][i]==fa)continue;
        else sum+=dfs(e[x][i],x);
    }
    return sum;
}
void getroot(int x,int fa)
{
    if(fa==0)
    {
        rt=0;
        rtmx=2e18;
    }
    s[x]=1;
    int mx=0;
    for(int i=0;i<e[x].size();i++)
    {
        int y=e[x][i];
        if(y==fa||v[y]==0)continue;
        getroot(y,x);
        s[x]+=s[y];
        mx=max(mx,s[y]);
    }
    mx=max(mx,sum-s[x]);
    if(mx<rtmx)
    {
        rt=x;
        rtmx=mx;
    }
}
int ask(int x,int y)
{
    cout<<"? "<<x<<" "<<y<<"\n";
    cout.flush();
    int r;
    cin>>r;
    return r;
}
void solve() {
    cin>>n;
    sum=n;
    for(int i=1;i<=n;i++)
    {
        e[i].clear();
        v[i]=1;
        s[i]=0;

    }
    for(int i=1;i<=n;i++)
    {
        int u,v;
        cin>>u>>v;
        if(u)
        {
            e[i].push_back(u);
            e[u].push_back(i);
        }
        if(v)
        {
            e[v].push_back(i);
            e[i].push_back(v);
        }
    }
    getroot(1,0);;
    while(1)
    {
        int x=0,y=0;
        for(int i=0;i<e[rt].size();i++)
        {
            if(!v[e[rt][i]])continue;
            if(!x)x=e[rt][i];
            else if(!y)y=e[rt][i];
        }
        if(!x&&!y)
        {
            cout<<"! "<<rt<<"\n";
            cout.flush();
            return;
        }
        else if(!y)
        {
            if(ask(rt,x)==0)
            {
                cout<<"! "<<rt<<"\n";
                cout.flush();
                return;
            }
            else
            {
                cout<<"! "<<x<<"\n";
                cout.flush();
                return;
            }
        }
        int vi=ask(x,y);
        if(vi==0)
        {
            v[rt]=0;
            sum=dfs(x,0);
            getroot(x,0);
        }
        else if(vi==1)
        {
            v[x]=0;
            v[y]=0;
            sum=dfs(rt,0);
            getroot(rt,0);
        }
        else
        {
            v[rt]=0;
            sum=dfs(y,0);
            getroot(y,0);
        }


    }
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 8884kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: