QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#733256	#9570. Binary Tree	ucup-team134^#	RE	0ms	11672kb	C++14	3.2kb	2024-11-10 17:56:05	2024-11-10 17:56:06

Judging History

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

[2024-11-10 17:56:06]
评测

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

查看

[2024-11-10 17:56:05]
提交

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){

    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){
        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);
        if(pom==-1)continue;
        return pom;
    }
    return -1;
}

int qry(int a,int  b){
    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--){

        scanf("%d",&n);
        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];
            int c=go(root,0);
            vector<int>cand;
            for(int i=0;i<vect[c].size();i++){
                int id=vect[c][i];
                if(gpos[id])continue;
                cand.pb(id);
            }

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

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

        }

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

    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 11672kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: