QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#752258#9570. Binary TreesyhyydsWA 1ms5888kbC++171.9kb2024-11-15 23:33:192024-11-15 23:33:20

Judging History

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

  • [2024-11-15 23:33:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5888kb
  • [2024-11-15 23:33:19]
  • 提交

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;
		cout << "? " << le[u] << " " << ri[u] << endl;
		cin >> t;
		cout.flush();
		if (!t) return le[u];
		if (t == 2) return ri[u];
		le[u] = 0;
		ri[u] = 0;
		return x;
	}
	if (le[u])
	{
		int t;
		cout << "? " << le[u] << " " << u << endl;
		cin >> t;
		cout.flush();
		if (!t) return le[u];
		le[u] = 0;
		return x;
	}
	int t;
	cout << "? " << ri[u] << " " << u << endl;
	cin >> t;
	cout.flush();
	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;
	x = 1;
	pa[0] = 0;
	while (pa[x] != 0) x = pa[x];
	while (1)
	{
		dfs(x);
		n = w[x];
		if (n == 1) break;
		int y = seek(x);
		x = y;
	}
	cout << x << endl;
	printf("! %d\n", x);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
		solve();
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5888kb

input:

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

output:

? 1 5
? 2 4
3

result:

wrong answer Token parameter [name=op] equals to "3", doesn't correspond to pattern "[?!]{1,1}" (test case 1)