QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#752253 | #9570. Binary Tree | syhyyds | TL | 0ms | 0kb | C++17 | 1.9kb | 2024-11-15 23:26:26 | 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