QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#732038	#9570. Binary Tree	quark404^#	RE	1ms	5592kb	C++20	3.5kb	2024-11-10 12:48:56	2024-11-10 12:48:59

Judging History

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

[2024-11-10 12:48:59]
评测

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

查看

[2024-11-10 12:48:56]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
vector<int> mp[200005];
void init()
{
    cin>>n;
    for(int i=1;i<=n;i++) mp[i].clear();
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x!=0)
        {
            mp[x].push_back(i);
            mp[i].push_back(x);
        }
        if(y!=0)
        {
            mp[y].push_back(i);
            mp[i].push_back(y);
        }
    }
    return;
}
int query(int x,int y)
{
    cout<<"? "<<x<<' '<<y<<endl;
    cout<<flush;
    int tmp;
    cin>>tmp;
    return tmp;
}
void print_ans(int x)
{
    cout<<"! "<<x<<endl;
    cout<<flush;
    return;
}
set<pair<int,int>> ban;
int dis[200005];
int from[200005];
int nodecnt=0;
pair<int,int> dfs_get_dis(int x,int fa)
{
    nodecnt++;
    dis[x]=dis[fa]+1;
    from[x]=fa;
    pair<int,int> tmp={x,dis[x]};
    for(int y:mp[x])
    {
        if(y==fa) continue;
        if(ban.count({x,y})==1) continue;
        auto r=dfs_get_dis(y,x);
        if(r.second>tmp.second) tmp=r;
    }
    return tmp;
}
void solve()
{
    if(n==1)
    {
        print_ans(1);
        return;
    }
    int can_cnt=0;
    for(int i=0;i<=20;i++)
    {
        if((1ll<<i)<=n) can_cnt=i;
        else break;
    }
    dis[0]=-1;
    ban.clear();
    int hav_point=1;
    int ans=-1;
    for(int i=1;i<=can_cnt;i++)
    {
        nodecnt=0;
        int p=dfs_get_dis(hav_point,0).first;
        if(nodecnt==1)
        {
            ans=p;
            break;
        }
        nodecnt=0;
        int q=dfs_get_dis(p,0).first;
        // cout<<"p,q="<<p<<" "<<q<<endl;
        int d=dis[q];
        // cout<<"d="<<d<<endl;
        int now=q;
        int k=query(p,q);
        for(int j=1;j<=(d+1)/2-1;j++) now=from[now];
        // cout<<"now="<<now<<endl;
        if(d&1)
        {
            if(k==0)
            {
                hav_point=p;
                ban.insert({now,from[now]});
                ban.insert({from[now],now});
            }
            else if(k==2)
            {
                hav_point=q;
                ban.insert({now,from[now]});
                ban.insert({from[now],now});
            }
            else while(true);
        }
        else
        {
            assert(d!=0);
            if(k==0)
            {
                now=from[now];
                hav_point=p;
                ban.insert({now,from[now]});
                ban.insert({from[now],now});
            }
            else if(k==1)
            {
                ban.insert({now,from[now]});
                ban.insert({from[now],now});
                now=from[now];
                hav_point=now;
                ban.insert({now,from[now]});
                ban.insert({from[now],now});
            }
            else if(k==2)
            {
                hav_point=q;
                ban.insert({now,from[now]});
                ban.insert({from[now],now});
            }
            else while(true);
        }
    }
    // cout<<"baned:"<<endl;
    // for(auto [x,y]:ban) cout<<x<<" "<<y<<endl;
    // cout<<"hav_point="<<hav_point<<endl;
    nodecnt=0;
    int p=dfs_get_dis(hav_point,0).first;
    if(nodecnt==1) ans=p;
    if(ans!=-1) print_ans(ans);
    else assert(false);
    return;
}

signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        init();
        solve();
    }
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 5592kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: