QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #729212 | #9570. Binary Tree | ucup-team5799# | RE | 0ms | 0kb | C++20 | 10.7kb | 2024-11-09 16:41:58 | 2024-11-09 16:42:04 |
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using LL = long long;
// struct node{
// int
// };
void solve() {
int n; cin >> n;
vector<vector<int>> e(n + 1);
for(int i = 1; i <= n; i++){
int a, b;
cin >> a >> b;
// cout << a << " " << b << endl;
if(a){e[a].push_back(i); e[i].push_back(a);}
if(b){e[b].push_back(i); e[i].push_back(b);}
}
vector<int> d1(n + 1);
int t1 = 0;
// vector<int> d1(n + 1);
auto dfs1 = [&](auto&& dfs1, int u, int f, int dis) -> void {
d1[u] = dis;
if(d1[u] > d1[t1]){t1 = u;}
for(auto v : e[u]){
if(v == f)continue;
dfs1(dfs1, v, u, dis + 1);
}
};
dfs1(dfs1, 1, 1, 1);
vector<int> d2(n + 1);
int t2 = 0;
auto dfs2 = [&](auto&& dfs2, int u, int f, int dis) -> void {
d2[u] = dis;
if(d2[u] > d2[t2]){t2 = u;}
for(auto v : e[u]){
if(v == f){continue;}
dfs2(dfs2, v, u, dis + 1);
}
};
dfs2(dfs2, t1, t1, 1);
t2 = (d2[t2] / 2) + 1;
int rot;
for(int i = 1; i <= n; i++){
if(t2 == d2[i]){rot = i; break;}
}
vector<int> fa(n + 1);
auto kk = [&](auto&& kk, int u, int f) -> void {
for(auto v : e[u]){
if(v == f)continue;
fa[v] = u;
kk(kk, v, u);
}
};
fa[rot] = rot;
kk(kk, rot, rot);
// cout << rot << endl;
bool ok = 0;
auto dfs = [&](auto&& dfs, int u, int f) -> void {
// cout << u << endl;
if(ok)return ;
if(u == rot && e[u].size() == 1){
int top = u;
// int temp =
vector<int> temp;
temp.push_back(u);
u = e[u][0];
while(e[u].size() == 2){
temp.push_back(u);
for(auto v : e[u]){
if(v == fa[u])continue;
else {
u = v;
break;
}
}
}
temp.push_back(u);
if(e[u].size() == 1){
int l = 0;
int r = (int)temp.size() - 1;
while(1){
cout << "? " << temp[l] << " " << temp[r] << endl;
int op;
cin >> op;
int idx = (int)temp.size() / 2;
if(op == 1){
cout << "! " << temp[idx] << endl;
ok = 1;
break;
}
else if(op == 2){
if(r - l <= 2){
cout << "! " << temp[r] << endl;
ok = 1;
break;
}
else{
l = idx;
}
}
else{
if(r - l <= 2){
cout << "! " << temp[l] << endl;
ok = 1;
break;
}
else{
r = idx;
}
}
}
return ;
}
else if (e[u].size() == 3) {
int le = e[u][0];
int ri = e[u][1];
if(le == fa[u]){le = e[u][2];}
if(ri == fa[u]){ri = e[u][2];}
cout << "? " << le << " " << ri << endl;
int op;
cin >> op;
if(op == 1){
int l = 0;
int r = (int)temp.size() - 1;
while(1){
cout << "? " << temp[l] << " " << temp[r] << endl;
int op;
cin >> op;
int idx = (int)temp.size() / 2;
if(op == 1){
cout << "! " << temp[idx] << endl;
ok = 1;
break;
}
else if(op == 2){
if(r - l <= 2){
cout << "! " << temp[r] << endl;
ok = 1;
break;
}
else{
l = idx;
}
}
else{
if(r - l <= 2){
cout << "! " << temp[l] << endl;
ok = 1;
break;
}
else{
r = idx;
}
}
}
return ;
}
else if(op == 0){
dfs(dfs, le, u);
}
else{
dfs(dfs, ri, u);
}
}
}
if(e[u].size() == 1){
cout << "! " << u << endl;
ok = 1;
return ;
}
else if(e[u].size() == 2){
int top = u;
// int temp =
vector<int> temp;
// temp.push_back(u);
// u = e[u][0];
while(e[u].size() == 2){
temp.push_back(u);
for(auto v : e[u]){
if(v == fa[u])continue;
else {
u = v;
break;
}
}
}
temp.push_back(u);
// for(auto v : temp){cout << v << " ";}cout << endl;
if(e[u].size() == 1){
int l = 0;
int r = (int)temp.size() - 1;
while(1){
cout << "? " << temp[l] << " " << temp[r] << endl;
int op;
cin >> op;
int idx = (int)temp.size() / 2;
if(op == 1){
cout << "! " << temp[idx] << endl;
ok = 1;
break;
}
else if(op == 2){
if(r - l <= 2){
cout << "! " << temp[r] << endl;
ok = 1;
break;
}
else{
l = idx;
}
}
else{
if(r - l <= 2){
cout << "! " << temp[l] << endl;
ok = 1;
break;
}
else{
r = idx;
}
}
}
return ;
}
else if (e[u].size() == 3) {
int le = e[u][0];
int ri = e[u][1];
if(le == fa[u]){le = e[u][2];}
if(ri == fa[u]){ri = e[u][2];}
cout << "? " << le << " " << ri << endl;
// ok = 1;
int op;
cin >> op;
if(op == 1){
int l = 0;
int r = (int)temp.size() - 1;
while(1){
cout << "? " << temp[l] << " " << temp[r] << endl;
int op;
cin >> op;
int idx = (int)temp.size() / 2;
if(op == 1){
cout << "! " << temp[idx] << endl;
ok = 1;
break;
}
else if(op == 2){
if(r - l <= 2){
cout << "! " << temp[r] << endl;
ok = 1;
break;
}
else{
l = idx;
}
}
else{
if(r - l <= 2){
cout << "! " << temp[l] << endl;
ok = 1;
break;
}
else{
r = idx;
}
}
}
return ;
}
else if(op == 0){
dfs(dfs, le, u);
}
else{
dfs(dfs, ri, u);
}
}
}
else if(e[u].size() == 3){
int le = e[u][0];
int ri = e[u][1];
if(le == fa[u]){le = e[u][2];}
if(ri == fa[u]){ri = e[u][2];}
cout << "? " << le << " " << ri << endl;
int op;
cin >> op;
if(op == 1){cout << "! " << u << endl; ok = 1; return ;}
else if(op == 2){dfs(dfs, ri, u);}
else if(op == 0){dfs(dfs, le, u);}
}
// int top = u;
// while(e[u])
};
// for(int i = 1; i <= n; i++){
// cout << i << "==";
// for(auto v : e[i]){cout << v << " ";}
// cout << endl;
// }
if(e[rot].size() == 2){
int le = e[rot][0];
int ri = e[rot][1];
cout << "? " << le << " " << ri << endl;
int op;
cin >> op;
if(op == 1){cout << "! " << 1 << endl; ok = 1; return ;}
else if(op == 0){dfs(dfs, le, rot);}
else if(op == 2){dfs(dfs, ri, rot);}
}
else if(e[rot].size() == 3){
int le = e[rot][0];
int ri = e[rot][1];
cout << "? " << le << " " << ri << endl;
int op;
cin >> op;
if(op == 1){
e[rot].erase(e[rot].begin());
e[rot].erase(e[rot].begin());
dfs(dfs, e[rot][0], rot);
}
else if(op == 0){dfs(dfs, le, rot);}
else if(op == 2){dfs(dfs, ri, rot);}
}
else {
dfs(dfs, rot, rot);
}
}
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
Runtime Error
input:
2 5 0 0 1 5 2 4 0 0 0 0 1 0
output:
? 1 5 ? 3 4 ! 3