QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#755283#9570. Binary TreeMaxduan#WA 0ms14632kbC++202.9kb2024-11-16 16:56:572024-11-16 16:56:57

Judging History

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

  • [2024-11-16 16:56:57]
  • 评测
  • 测评结果：WA
  • 用时：0ms
  • 内存：14632kb
查看
  • [2024-11-16 16:56:57]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define maxn 200005
int siz[maxn],mx[maxn];
set<int>g[maxn];
int all;
int zx=0,mm=1e9;
int n;

void findrt(int u,int fa){
    siz[u]=1;
    mx[u]=0;
    for(auto v:g[u]){
        if(v==fa)continue;
        findrt(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }
    mx[u]=max(mx[u],all-siz[u]);
    if(mx[u]<mm){
        zx=u;
        mm=mx[u];
    }
}

void dfs(int u,int fa){
    siz[u]=1;
    for(auto v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
}

/*

2
2 3
0 0
0 0

*/

void solve(){
    cin>>n;
    all=n;
    for(int i=1;i<=n;i++){
        int a,b;cin>>a>>b;
        if(a){
            g[i].insert(a);
            g[a].insert(i);
        }
        if(b){
            g[i].insert(b);
            g[b].insert(i);
        }
    }
    zx=1;
    while(1){
        mm=1e9;
        findrt(zx,0);
        dfs(zx,0);
        vector<int>vt;
        //for(int i=1;i<=3;i++){
        //    cout<<siz[i]<<' '<<mx[i]<<'\n';
        //}
        //cout<<"zx siz="<<zx<<' '<<siz[zx]<<'\n';
        for(auto v:g[zx]){
            vt.push_back(v);
        }
        if(vt.size()==3){
            cout<<"? "<<vt[0]<<' '<<vt[1]<<endl;
            int ans;cin>>ans;
            if(ans==1){
                all-=siz[vt[0]]+siz[vt[1]];
                g[zx].erase(vt[0]);
                g[zx].erase(vt[1]);
                continue;
            }

            if(ans==2){
                swap(vt[0],vt[1]);
            }
            all-=siz[zx]-siz[vt[0]];
            g[vt[0]].erase(zx);
            zx=vt[0];
        }
        else if(vt.size()==2){
            cout<<"? "<<vt[0]<<' '<<vt[1]<<endl;
            int ans;cin>>ans;
            if(all==3){
                if(ans==0){
                    cout<<"! "<<vt[0]<<endl;
                }
                else if(ans==2){
                    cout<<"! "<<vt[1]<<endl;
                }
                else cout<<"! "<<zx<<endl;
                return;
            }
            if(ans==1){
                cout<<"! "<<zx<<endl;
                return;
            }
            if(ans==2){
                swap(vt[0],vt[1]);
            }
            all-=siz[zx]-siz[vt[0]];
            g[vt[0]].erase(zx);
            zx=vt[0];
        }
        else if(vt.size()==1){
            cout<<"? "<<zx<<' '<<vt[0]<<endl;
            int ans;cin>>ans;
            if(ans==0){
                cout<<"! "<<zx<<endl;
            }
            else{
                cout<<"! "<<vt[0]<<endl;
            }
            return;
        }
        else{
            cout<<"! "<<zx<<endl;
            return;
        }
    }
    
}

signed main(){
    int TT=1;cin>>TT;
    while(TT--){
        solve();
        for(int i=1;i<=n;i++){
            g[i].clear();
        }
    }
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 14632kb

input:

2
5
0 0
1 5
2 4
0 0
0 0
2
0
2
0 2
0 0
2

output:

? 1 3
? 4 3
! 4
? 2 1
! 1

result:

ok OK (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 12984kb

input:

5555
8
2 0
8 6
0 0
3 0
0 0
7 0
0 0
5 4
0
0
2
8
0 0
1 4
2 0
0 0
7 8
0 0
3 0
6 0
0
1
0
8
5 8
0 0
1 7
0 0
0 0
4 2
0 0
6 0
0
0
2
5
4 5
3 1
0 0
0 0
0 0
0
2
8
0 0
0 0
5 6
0 0
1 4
2 0
3 8
0 0
0
0
5
3 0
5 1
0 0
0 0
4 0
0
2
5
5 0
0 0
0 0
3 0
2 4
1
0
3
3 0
1 0
0 0
2
2
2 0
0 0
0
3
2 3
0 0
0 0
2
10
2 8
9 7
0 0
...

output:

? 2 4
? 2 7
? 1 2
! 2
? 3 5
? 1 3
? 4 2
! 4
? 1 6
? 1 7
? 5 1
! 1
? 2 4
? 3 2
! 2
? 5 6
? 1 4
! 1
? 1 5
? 3 1
! 1
? 1 2
? 3 5
! 3
? 2 3
! 3
? 2 1
! 2
? 2 3
! 3
? 2 5
? 1 9
? 10 9
! 9
? 2 1
! 2
? 5 9
? 4 5
? 8 3
! 8
? 5 8
? 1 5
? 3 9
! 7
? 3 4
? 1 7
? 2 8
! 8
? 2 1
! 1
? 3 4
? 1 7
! 7
? 4 5
? 2 3
? 4...

result:

wrong answer Too many queries (test case 44)
English 繁體中文 简体中文

服务器时间: 2025-01-21 15:39:44 | 开源项目