QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #749451 | #9570. Binary Tree | rea_lity | ML | 4ms | 10272kb | C++23 | 7.4kb | 2024-11-15 00:54:55 | 2024-11-15 00:54:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(),(x).end()
#define l first
#define r second
#define MYDEBUG1 //note: close the debug before submit
#ifdef MYDEBUG
#define Debug(X) cout << #X << ": " << X << ";" << endl
template <typename T>
void debug(vector<T>&nums,int len){
if(nums.size() + 1 < len)cout << "Overflow: size of anrry is <" << nums.size() << ">,but len is <" << len << ">" << endl;
else for(int i = 0;i <= len;i++)cout << nums[i] << " \n"[i == len];
}
#else
#define Debug(X)
template <typename T>
void debug(vector<T>&nums,int len){}
#endif
const int N = 2e5 + 10;
vector<int>mp[N],siz(N),wt(N),tmp[N];
int n,rt,isRes,m,f[N];
void getCentroid(int u, int fa) {
siz[u] = 1;
wt[u] = 0;
for (int v : mp[u]) {
if (v != fa) {
f[v] = u;
getCentroid(v, u);
siz[u] += siz[v];
wt[u] = max(wt[u], siz[v]);
}
}
wt[u] = max(wt[u], m - siz[u]);
if (rt == 0 || wt[u] < wt[rt]) rt = u; // rt 为重心编号
}
void upmp(int u,int fa){
for(int v : mp[u]){
if(v == fa) continue;
tmp[u].push_back(v);
tmp[v].push_back(u);
}
}
void dfs(int x){
if(isRes)return;
rt = 0;
getCentroid(x,0);
/* cout << "zhong:" << rt << endl;
cout.flush(); */
if(mp[rt].size() == 0){
cout << "! " << rt << endl;
cout.flush();
isRes = 1;
return;
}
else if(mp[rt].size() == 1){
cout << "? " << mp[rt][0] << " " << rt << endl;
cout.flush();
int t;cin >> t;
cout << "! " << (t == 0 ? mp[rt][0] : rt) << endl;
cout.flush();
isRes = 1;
return;
}
else if(mp[rt].size() == 2){
int lt;
if(wt[mp[rt][0]] <= wt[rt]){
lt = mp[rt][0];
}
else{
lt = mp[rt][1];
}
cout << "? " << lt << " " << rt << endl;
cout.flush();
int t;cin >> t;
int tx = (t == 0 ? lt : rt),ty = (t != 0 ? lt : rt);
for(int i = 1;i <= n;i++)tmp[i].clear();
upmp(tx,ty);m = 0;
for(int i = 1;i <= n;i++){
mp[i].clear();
mp[i] = tmp[i];
if(tmp[i].size())m ++;
}
dfs(tx);
}
else if(mp[rt].size() == 3){
vector<pair<int,int>>vv;
for(int i = 0;i < 3;i++){
int xx = (f[mp[rt][i]] == rt ? siz[mp[rt][i]] : m - siz[rt]);
vv.push_back({xx,i});
}
sort(all(vv),greater<pair<int,int>>());
int a = mp[rt][vv[0].r],b = mp[rt][vv[1].r];
cout << "? " << a << " " << b << endl;
cout.flush();
int t,lt,tx;cin >> t;
if(t == 0){
lt = a;
tx = lt;
}
else if(t == 1){
lt = mp[rt][vv[2].r];
tx = rt;
}
else lt = b,tx = lt;
for(int i = 1;i <= n;i++)tmp[i].clear();
if(t == 1)tmp[lt].push_back(rt);tmp[rt].push_back(lt);
upmp(lt,rt);m = 0;
for(int i = 1;i <= n;i++){
mp[i].clear();
mp[i] = tmp[i];
if(tmp[i].size())m ++;
}
/* for(int i = 1;i <= n;i++){
cout << i << " ";
for(int vv : mp[i])cout << vv << " ";
cout << endl;
} */
dfs(tx);
}
}
/*
3
2 4
1 5
*/
void solve()
{
cin >> n;m = n;
for(int i = 1;i <= n;i++){
mp[i].clear();
tmp[i].clear();
}
for(int i = 1;i <= n;i++){
int a,b;cin >> a >> b;
if(a)mp[i].push_back(a),mp[a].push_back(i);
if(b)mp[i].push_back(b),mp[b].push_back(i);
}isRes = 0;
dfs(1);
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
while (T--)solve();
return 0;
}
/*
_____ _____ _____ _____ _____ _____ _____
/\ \ /\ \ /\ \ /\ \ /\ \ /\ \ |\ \
/::\ \ /::\ \ /::\ \ /::\____\ /::\ \ /::\ \ |:\____\
/::::\ \ /::::\ \ /::::\ \ /:::/ / \:::\ \ \:::\ \ |::| |
/::::::\ \ /::::::\ \ /::::::\ \ /:::/ / \:::\ \ \:::\ \ |::| |
/:::/\:::\ \ /:::/\:::\ \ /:::/\:::\ \ /:::/ / \:::\ \ \:::\ \ |::| |
/:::/__\:::\ \ /:::/__\:::\ \ /:::/__\:::\ \ /:::/ / \:::\ \ \:::\ \ |::| |
/::::\ \:::\ \ /::::\ \:::\ \ /::::\ \:::\ \ /:::/ / /::::\ \ /::::\ \ |::| |
/::::::\ \:::\ \ /::::::\ \:::\ \ /::::::\ \:::\ \ /:::/ / ____ /::::::\ \ /::::::\ \ |::|___|______
/:::/\:::\ \:::\____\ /:::/\:::\ \:::\ \ /:::/\:::\ \:::\ \ /:::/ / /\ \ /:::/\:::\ \ /:::/\:::\ \ /::::::::\ \
/:::/ \:::\ \:::| |/:::/__\:::\ \:::\____\/:::/ \:::\ \:::\____\/:::/____/ /::\ \/:::/ \:::\____\ /:::/ \:::\____\ /::::::::::\____\
\::/ |::::\ /:::|____|\:::\ \:::\ \::/ /\::/ \:::\ /:::/ /\:::\ \ \:::\ /:::/ \::/ / /:::/ \::/ / /:::/~~~~/~~
\/____|:::::\/:::/ / \:::\ \:::\ \/____/ \/____/ \:::\/:::/ / \:::\ \ \:::\/:::/ / \/____/ /:::/ / \/____/ /:::/ /
|:::::::::/ / \:::\ \:::\ \ \::::::/ / \:::\ \ \::::::/ / /:::/ / /:::/ /
|::|\::::/ / \:::\ \:::\____\ \::::/ / \:::\ \ \::::/____/ /:::/ / /:::/ /
|::| \::/____/ \:::\ \::/ / /:::/ / \:::\ \ \:::\ \ \::/ / \::/ /
|::| ~| \:::\ \/____/ /:::/ / \:::\ \ \:::\ \ \/____/ \/____/
|::| | \:::\ \ /:::/ / \:::\ \ \:::\ \
\::| | \:::\____\ /:::/ / \:::\____\ \:::\____\
\:| | \::/ / \::/ / \::/ / \::/ /
\|___| \/____/ \/____/ \/____/ \/____/
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 10272kb
input:
2 5 0 0 1 5 2 4 0 0 0 0 1 0 2 0 2 0 0 2
output:
? 3 5 ? 2 1 ! 2 ? 1 2 ! 2
result:
ok OK (2 test cases)
Test #2:
score: -100
Memory Limit Exceeded
input:
5555 8 2 0 8 6 0 0 3 0 0 0 7 0 0 0 5 4 0 2 0 8 0 0 1 4 2 0 0 0 7 8 0 0 3 0 6 0 2 2
output:
? 2 4 ? 6 2 ? 2 1 ! 2 ? 3 7 ? 7 5 ! 5