QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#756700	#9570. Binary Tree	kalikari	TL	2ms	9892kb	C++17	3.7kb	2024-11-16 21:36:17	2024-11-16 21:36:22

Judging History

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

[2024-11-16 21:36:22]
评测

测评结果：TL
用时：2ms
内存：9892kb

查看

[2024-11-16 21:36:17]
提交

answer

#include<bits/stdc++.h>
using namespace std;
/*
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
*/
// #define int long long
#define ld long double
//#define INT __int128
#define eb(x) emplace_back(x)
#define fi first
#define se second
#define sc(x) scanf("%d",&x)
#define SC(x) scanf("%lld",&x)
#define reserve reserve
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<long long, long long> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const ld eps = 1e-12;
const int N = 5e5 + 10, M = N + 10;
int n;
int l[N],r[N],siz[N],fa[N];
int root,tg;

void dfs(int u){
    siz[u]=1;
    if(l[u]){
        dfs(l[u]);
        siz[u]+=siz[l[u]];
    }
    if(r[u]){
        dfs(r[u]);
        siz[u]+=siz[r[u]];
    }
    if(tg)return;
    if(siz[l[u]]<=n/2&&siz[r[u]]<=n/2&&n-siz[u]+1<=n/2&&l[u]&&r[u]){
        tg=1;
        printf("? %d %d\n",l[u],r[u]);
        fflush(stdout);
        int op=3;
        scanf("%d",&op);
        if(op==0){
            root=l[u];
            fa[l[u]]=0;
            n=siz[l[u]];
        }
        else if(op==1){
            int sm=siz[l[u]]+siz[r[u]];
            siz[u]-=sm;
            n-=sm;
            l[u]=0,r[u]=0;
        }
        else if(op==2){
            root=r[u];
            fa[r[u]]=0;
            n=siz[r[u]];
        }
        return;
    }
    if(siz[l[u]]<=n/2&&siz[r[u]]+1<=n/2&&n-siz[u]<=n/2&&fa[u]&&l[u]){
        tg=1;
        printf("? %d %d\n",fa[u],l[u]);
        fflush(stdout);
        int op=3;
        scanf("%d",&op);
        if(op==0){
            int f=fa[u];
            n-=siz[u];
            siz[u]=0;
            if(l[f]==u){
                l[f]=0;
            }
            else{
                r[f]=0;
            }
        }
        else if(op==1){
            root=u;
            n=siz[u]-siz[l[u]];
            l[u]=0;
            fa[u]=0;
        }
        else if(op==2){
            root=l[u];
            n=siz[l[u]];
            fa[l[u]]=0;
        }
        return;
    }
    if(siz[r[u]]<=n/2&&siz[l[u]]+1<=n/2&&n-siz[u]<=n/2&&fa[u]&&r[u]){
        tg=1;
        printf("? %d %d\n",fa[u],r[u]);
        fflush(stdout);
        int op=3;
        scanf("%d",&op);
        if(op==0){
            n-=siz[u];
            int f=fa[u];
            if(l[f]==u){
                l[f]=0;
            }
            else{
                r[f]=0;
            }
        }
        else if(op==1){
            root=u;
            fa[u]=0;
            n=siz[u]-siz[l[u]];
        }
        else if(op==2){
            root=r[u];
            n=siz[r[u]];
            fa[r[u]]=0;
        }
        return;
    }
}

void solve(){
    cin>>n;
    // cout<<"---------"<<n<<endl;
    for(int i=1;i<=n+2;i++){
        fa[i]=0;
    }
    for(int i=1;i<=n;i++){
        scanf("%d %d",&l[i],&r[i]);
        if(l[i])fa[l[i]]=i;
        if(r[i])fa[r[i]]=i;
    }
    for(int i=1;i<=n;i++){
        // cout<<"______"<<i<<" "<<fa[i]<<endl;
        if(!fa[i])root=i;
    }
    while(n>2){
        tg=0;
        dfs(root);
    }
    if(n==1){
        printf("! %d",root);
    }
    else{
        printf("? %d %d\n",root,l[root]?l[root]:r[root]);
        fflush(stdout);
        int op=3;
        scanf("%d",&op);
        if(op==0){
            printf("! %d\n",root);
        }
        else if(op==2){
            printf("! %d\n",l[root]?l[root]:r[root]);
        }
    }
}

signed main(){
    // ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T=1,cas=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 9892kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Time Limit Exceeded

input:

output: