QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#733321	#9570. Binary Tree	ucup-team134^#	TL	3ms	12396kb	C++14	3.6kb	2024-11-10 18:16:48	2024-11-10 18:16:50

Judging History

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

[2024-11-10 18:16:50]
评测

测评结果：TL
用时：3ms
内存：12396kb

查看

[2024-11-10 18:16:48]
提交

answer

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}


const int maxn=3e5+10;
int n,nsz;
vector<int>vect[maxn];
int gpos[maxn],sz[maxn];
void precalc(int x,int prv){
    sz[x]=1;
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        if(id==prv || gpos[id])continue;
        precalc(id,x);
        sz[x]+=sz[id];
    }
}
int go(int x,int prv, vector<pii>&cand){

    int mx=nsz/2;
    bool e=1;
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        if(id==prv || gpos[id])continue;
        if(mx<sz[id])e=0;
    }
    if(nsz-sz[x]>mx)e=0;
    if(e){
        for(int i=0;i<vect[x].size();i++){
            int id=vect[x][i];
            if(id==prv || gpos[id])continue;
            cand.pb({sz[id],id});
        }
        if(prv!=0)cand.pb({nsz-sz[x],prv});
        return x;
    }

    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        if(id==prv || gpos[id])continue;
        int pom = go(id,x,cand);
        if(pom==-1)continue;
        return pom;
    }
    return -1;
}

int cnt=0;
int goalcnt;
int qry(int a,int b){
    cnt++;
    if(cnt>goalcnt){
        while(1){}
    }

    printf("? %d %d\n",a,b);
    fflush(stdout);
    int ret;
    scanf("%d",&ret);
    return ret;
}

int main(){

    ///freopen("test.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){

        cnt=0;
        scanf("%d",&n);
        goalcnt=0;
        int nn=n;
        while(nn>0){
            nn>>=1;
            goalcnt++;
        }
        goalcnt--;

        for(int i=1;i<=n;i++)gpos[i]=0;
        for(int i=1;i<=n;i++){
            vect[i].clear();
        }
        for(int i=1;i<=n;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            if(a!=0){
                vect[i].pb(a);
                vect[a].pb(i);
            }
            a=b;
            if(a!=0){
                vect[i].pb(a);
                vect[a].pb(i);
            }
        }

        int root=1;
        int rez=-1;
        while(1){
            precalc(root,0);
            if(sz[root]==1){
                rez=root;
                break;
            }
            nsz=sz[root];
            vector<pii>cand;
            sort(cand.begin(),cand.end());
            reverse(cand.begin(),cand.end());
            int c=go(root,0,cand);

            if(cand.size()==1){
                int pom=qry(c,cand[0].ss);
                if(pom==0)rez=c;
                else rez=cand[0].ss;
                break;
            }

            int pom=qry(cand[0].ss,cand[1].ss);
            if(pom==0){
                gpos[c]=1;
                root=cand[0].ss;
                continue;
            }
            if(pom==1){
                gpos[cand[0].ss]=1;
                gpos[cand[1].ss]=1;
                root=c;
                continue;
            }
            if(pom==2){
                gpos[c]=1;
                root=cand[1].ss;
                continue;
            }

        }

        printf("! %d\n",rez);
        fflush(stdout);
    }

    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 12396kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Time Limit Exceeded

input:

output: