QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#752253#9570. Binary TreesyhyydsTL 0ms0kbC++171.9kb2024-11-15 23:26:262024-11-15 23:26:26

Judging History

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

  • [2024-11-15 23:26:26]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-11-15 23:26:26]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <math.h>
#include <map>
#include <sstream>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <climits>
using namespace std;
#define   LL long long
#define ls o<<1
#define rs o<<1|1
#define PII pair<int,int>
#define PPI pair<pair<int,int>,int >
const int N =2e5+100;
const LL  mod = 998244353;
const LL MAX=1e18;
int w[N],le[N],ri[N];
int n,x,pa[N];
void dfs(int u) 
{
	w[u] = 1;
	if (le[u])
	{   
		dfs(le[u]);
		w[u] += w[le[u]];
	}
	if (ri[u]) 
	{
		dfs(ri[u]);
		w[u] += w[ri[u]];
	}
}
int seek(int u) 
{ 
	if (2 * w[le[u]]>n)
		return seek(le[u]);
	if (2 * w[ri[u]] > n)
		return seek(ri[u]);
	if (le[u] && ri[u]) 
	{
		int t;
		printf("? %d %d \n", le[u],ri[u]);
		scanf("%d", &t);
		fflush(stdout);
		if (!t) return le[u];
		if (t == 2) return ri[u];
			le[u] = 0;
			ri[u] = 0;
			return x;
	}
	if (le[u]) 
	{
		int t;
		printf("? %d %d \n", le[u],u);
		scanf("%d", &t);
		fflush(stdout);
		if (!t) return le[u];
		le[u] = 0;
		return x;
	}
		int t;
		printf("? %d %d \n", ri[u],u);
		scanf("%d", &t);
		fflush(stdout);
		if (!t) return ri[u];
		ri[u] = 0;
		return x;
}
void solve() 
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) pa[i]=0;
	for (int i = 1; i <= n; i++)
    scanf("%d%d", &le[i], &ri[i]),pa[le[i]]=i,pa[ri[i]]=i;
	pa[0] = 0;
    x = 1;
	while (pa[x] != 0) x = pa[x];
	while (1) 
	{
		dfs(x);
		n = w[x];
		if (n == 1) break;
		int y = seek(x);
		x = y;
	}
	printf("! %d\n", x);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

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

output:


result: