QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#736040	#9570. Binary Tree	xbzxzn	RE	2ms	6052kb	C++17	3.5kb	2024-11-11 23:44:16	2024-11-11 23:44:23

Judging History

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

[2024-11-11 23:44:23]
评测

测评结果：RE
用时：2ms
内存：6052kb

查看

[2024-11-11 23:44:16]
提交

answer

#include<bits/stdc++.h>
//#define int long long int
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e5+5;
const int inf=1e18;
int n;
vector<int>edge[maxn];int cnt=0;
int ask(int u,int v)
{
    cout<<"? "<<u<<" "<<v<<endl;cnt++;
    int vv;cin>>vv;
    return vv;
}
int dep[maxn];
bool vis[maxn];
void dfs(int x,int pre)
{
    dep[x]=dep[pre]+1;
    for(auto j:edge[x])
    {
        if(j==pre||vis[j])continue;
        dfs(j,x);
    }
}
vector<int>g;int aim;
bool dfs2(int x,int pre)
{
    if(x==aim)
        return true;
    for(auto j:edge[x])
    {
        if(j==pre||vis[j])continue;
        if(dfs2(j,x))
        {
            g.pb(j);
            return true;
        }
    }
    return false;
}
void dfs3(int x,int pre)
{
    vis[x]=true;
    for(auto j:edge[x])
    {
        if(j==pre||vis[j])continue;
        dfs3(j,x);
    }
}
void solve()
{
    cin>>n;int u=0;cnt=0;
    while((1<<u)<=n)
        u++;
    u--;
    for(int i=1;i<=n;i++)
    {
        edge[i].clear();vis[i]=false;
    }
    for(int i=1;i<=n;i++)
    {
        int x,y;cin>>x>>y;
        if(x)
        {
            edge[i].pb(x);
            edge[x].pb(i);
        }
        if(y)
        {
            edge[i].pb(y);
            edge[y].pb(i);
        }
    }
    bool flag=true;
    while(flag)
    {
        g.clear();
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                dfs(i,0);break;
            }
        }
        int maxp=0;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                if(dep[i]>dep[maxp])
                {
                    maxp=i;
                }
            }
        }
        dfs(maxp,0);
        int qi=maxp;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                if(dep[i]>dep[maxp])
                {
                    maxp=i;
                }
            }
        }
        aim=maxp;
        dfs2(qi,0);
        g.pb(qi);
//        for(auto j:g)
//            cout<<j<<' ';cout<<endl;
        if(g.size()%2==0)
        {
            int mid=(int)g.size()/2;
            int op=ask(g[mid-1],g[mid]);
            if(op==0)
            {
                dfs3(g[mid],g[mid-1]);
            }
            else
            {
                dfs3(g[mid-1],g[mid]);
            }

        }
        else
        {
            if(g.size()==1)
            {
                cout<<"! "<<g[0]<<endl;return ;
            }
            else
            {
                int mid=(int)g.size()/2;
                int op=ask(g[mid-1],g[mid+1]);
                if(op==1)
                {
                    dfs3(g[mid-1],g[mid]);
                    dfs3(g[mid+1],g[mid]);
                }
                else if(op==0)
                {
                    dfs3(g[mid+1],g[mid]);
                    dfs3(g[mid],g[mid-1]);
                }
                else if(op==2)
                {
                    dfs3(g[mid-1],g[mid]);
                    dfs3(g[mid],g[mid+1]);
                }
            }
        }
        if(cnt>u)
        {
            cout<<"! "<<1<<endl;
            return ;
        }
    }
}
signed main()
{
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    cout.tie(nullptr);
    cout<<fixed<<setprecision(10);
    int T=1;
    cin>>T;
    for(int i=1;i<=T;i++)
        solve();
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 6052kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: