QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#778018#9570. Binary TreeLanthanmumRE 1ms3500kbC++202.5kb2024-11-24 12:09:412024-11-24 12:09:42

Judging History

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

  • [2024-11-24 12:09:42]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3500kb
  • [2024-11-24 12:09:41]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 1e5 + 9;
int n;
int flag;
int del[N];
vector<int> e[N];

int ask(int u, int v) {
    cout << "?" << " " << u << " " << v << endl;
    int x;
    cin >> x;
    return x;
};

void ok(int x) {
    cout << "!" << " " << x << endl;
    flag=1;
};
void add(int u,int v){
	e[u].push_back(v);
	e[v].push_back(u);
}
int get_size(int u,int f){
	if(del[u])return 0;
	int res=1;
	for(auto & i : e[u]){
		if(i==f)continue;
		res+=get_size(i,u);
	}
	return res;
}
int get_root(int u,int f,int tot,int &rt){
	if(del[rt])return 0;
	int sum=1,mx=0;
	for(auto & i : e[u]){
		if(i==f){
			continue;
		}
		int sz=get_root(i,u,tot,rt);
		mx=max(mx,sz);
		sum+=sz;
	}
	mx=max(mx,tot-sum);
	if(mx<=(tot/2)){
		rt=u;
	}
	return sum;
}
void dfs(int rt){
	if(del[rt])return;
	if(flag)return;
	int tot=get_size(rt,0);
	get_root(rt,0,tot,rt);
	vi t;
	for(auto & i : e[rt]){
		if(!del[i]){
			t.push_back(i);	
		}
	}
	int SZ=t.size();
	if(!SZ){
		ok(rt);
		return;
	}else if(SZ==1){
		int x=ask(rt,t[0]); 	
		if(!x){
			ok(rt);
			return;
		}else{
			ok(t[0]);
			return;
		}
	}else if(SZ==2){
		int x = ask(t[0], t[1]);
        if (x == 1) {
            ok(rt);
            flag = 1;
            return;
        }
        del[rt] = 1;
        if (!x) {
            dfs(t[0]);
            return;
        }
        dfs(t[1]);
        return;
		// int x=ask(t[0],t[1]);
		// if(!x){
			// del[rt]=1;
			// dfs(t[0]);
			// return;
		// }else if(x==1){
			// ok(rt);
			// return;
		// }else{
			// del[rt]=1;
			// dfs(t[1]);
			// return;
		// }
	}else{
		vector<pii> v;
		for(int i=0;i<3;i++){
			v.push_back({t[i],get_size(t[i],rt)});
		}
		sort(v.begin(),v.end(),[](const pii &a,const pii &b){
			return a.second>b.second;
		});
		vi tt;
		for(auto &[x,y] : v){
			tt.push_back(x);
		}
		int x=ask(tt[0],tt[1]);
		if(!x){
			del[rt]=1;
			dfs(tt[0]);
			return;
		}else if(x==1){
			del[tt[0]]=del[tt[1]]=1;
			dfs(rt);
			return;
		}else{
			del[rt]=1;
			dfs(tt[1]);	
			return;	
		}
	}
}
void clear(){
	for(int i=1;i<=n;i++){
		del[i]=0,e[i].clear();
	}
}
void solve(){
	cin>>n;
	clear();
	for(int i=1;i<=n;i++){
		int u,v;
		cin>>u>>v;
		if(u)add(u,i);
		if(v)add(v,i);
	}
	dfs(1);
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        flag = 0;
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3500kb

input:

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

output:

? 3 1
? 2 5
! 2
? 1 2
! 2

result:

ok OK (2 test cases)

Test #2:

score: -100
Runtime Error

input:

5555
8
2 0
8 6
0 0
3 0
0 0
7 0
0 0
5 4
0
0
0

output:

? 8 6
? 8 6
? 8 6
? 8 6

result: