QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #751265 | #9570. Binary Tree | ucup-team5799 | WA | 1ms | 3616kb | C++14 | 4.1kb | 2024-11-15 17:47:22 | 2024-11-15 17:47:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct node{
int to;
int id;
};
void solve(){
int n;
cin >> n;
vector<vector<node>> e(n + 1);
int times = 0;
vector<int> vi(n * 5);
for(int i = 1; i <= n; i++){
int a, b;
cin >> a >> b;
if(a != 0){
e[a].push_back({i, ++times});
e[i].push_back({a, times});
vi[times] = 1;
}
if(b != 0){
e[i].push_back({b, ++times});
e[b].push_back({i, times});
vi[times] = 1;
}
}
auto getsize = [&](auto&& getsize, int u, int f) -> int {
int x = 1;
for(auto [v, id] : e[u]){
if(v == f)continue;
if(vi[id] == 0)continue;
x += getsize(getsize, v, u);
}
return x;
};
auto find = [&](int x) -> int {
vector<int> fa(n + 1);
vector<int> ans(n + 1);
vector<int> siz(n + 1);
vector<int> big(n + 1);
auto dfs = [&](auto&& dfs, int u) -> void {
// cout << u << endl;
siz[u] = 1;
ans[u] = u;
for(auto [v, id] : e[u]){
if(vi[id] == 0)continue;
if(fa[u] == v){continue;}
fa[v] = u;
dfs(dfs, v);
siz[u] += siz[v];
big[u] = max(big[u], siz[v]);
}
for(auto [v, id] : e[u]){
if(vi[id] == 0)continue;
if(fa[u] == v){continue;}
int p = ans[v];
while(p != u){
if(max(big[p], siz[u] - siz[p]) <= siz[u] / 2){
ans[u] = p;
break;
}else{
p = fa[p];
}
}
}
};
fa[x] = x;
dfs(dfs, x);
return ans[x];
};
auto work = [&](auto&& work, int u) -> void {
// cout << "aaaaa" << endl;
u = find(u);
int cnt = 0;
vector<node> temp;
for(auto [v, id] : e[u]){
if(vi[id]){cnt++; temp.push_back({v, id});}
}
if(cnt == 0){cout << "! " << u << endl;}
else if(cnt == 1){
int f = temp[0].to;
cout << "? " << f << " " << u << endl;
int op;
cin >> op;
if(op == 0){cout << "! " << f << endl;return ;}
else if(op == 2){cout << "! " << u << endl; return ;}
}
else if(cnt == 2){
int f = temp[0].to;
int v = temp[1].to;
cout << "? " << f << " " << v << endl;
int op;
cin >> op;
if(op == 1){
cout << "! " << u << endl;
return ;
}
else if(op == 0){
vi[temp[0].id] = 0;
work(work, f);
}
else if(op == 2){
vi[temp[1].id] = 0;
work(work, v);
}
}
else if(cnt == 3){
vector<pair<int, pair<int, int>>> tt;
for(auto [v, id] : e[u]){
tt.push_back({getsize(getsize, v, u), {v, id}});
}
sort(tt.begin(), tt.end());
int f = tt[2].second.first;
int v = tt[1].second.first;
cout << "? " << f << " " << v << endl;
int op;
cin >> op;
if(op == 1){
vi[tt[1].second.second] = 0;
vi[tt[2].second.second] = 0;
work(work, u);
}
else if(op == 0){
vi[tt[2].second.second] = 0;
work(work, f);
}
else if(op == 2){
vi[tt[1].second.second] = 0;
work(work, v);
}
}
};
//work(work, 1);
for(int i = 1; i <= 500; i++){
cout << "? " << 1 << " " << 2 <<endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3616kb
input:
2 5 0 0 1 5 2 4 0 0 0 0 2 2
output:
? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ? 1 2 ...
result:
wrong answer Too many queries (test case 1)