QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #729906 | #9570. Binary Tree | ucup-team5799# | RE | 1ms | 3840kb | C++14 | 10.9kb | 2024-11-09 17:59:57 | 2024-11-09 18:00:01 |
Judging History
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);
int ppp;
for(auto v : e[u]){
if(v == fa[u])continue;
else {
ppp = v;
break;
}
}
u = ppp;
}
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 = (l + r) / 2;
if(op == 1){
cout << "! " << temp[idx] << endl;
ok = 1;
return;
}
else if(op == 2){
if(r - l <= 2){
cout << "! " << temp[r] << endl;
ok = 1;
return;
}
else{
l = idx;
}
}
else{
if(r - l <= 2){
cout << "! " << temp[l] << endl;
ok = 1;
return;
}
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 = (l + r) / 2;
if(op == 1){
cout << "! " << temp[idx] << endl;
ok = 1;
return;
}
else if(op == 2){
if(r - l <= 2){
cout << "! " << temp[r] << endl;
ok = 1;
return;
}
else{
l = idx;
}
}
else{
if(r - l <= 2){
cout << "! " << temp[l] << endl;
ok = 1;
return;
}
else{
r = idx;
}
}
}
return ;
}
else if(op == 0){
dfs(dfs, le, u);
}
else{
dfs(dfs, ri, u);
}
}return;
}
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);
int ooo;
for(auto v : e[u]){
if(v == fa[u])continue;
else {
ooo = v;
break;
}
}
u = ooo;
}
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 = (r + l) / 2;
if(op == 1){
cout << "! " << temp[idx] << endl;
ok = 1;
return;
}
else if(op == 2){
if(r - l <= 2){
cout << "! " << temp[r] << endl;
ok = 1;
return;
}
else{
l = idx;
}
}
else{
if(r - l <= 2){
cout << "! " << temp[l] << endl;
ok = 1;
return;
}
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 = (r + l) / 2;
if(op == 1){
cout << "! " << temp[idx] << endl;
ok = 1;
return;
}
else if(op == 2){
if(r - l <= 2){
cout << "! " << temp[r] << endl;
ok = 1;
return;
}
else{
l = idx;
}
}
else{
if(r - l <= 2){
cout << "! " << temp[l] << endl;
ok = 1;
return;
}
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 << "! " << rot << 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());
int ooo = e[rot][2];
e[rot].clear();
e[rot].push_back(ooo);
dfs(dfs, rot, rot);
}
else if(op == 0){dfs(dfs, le, rot);}
else if(op == 2){dfs(dfs, ri, rot);}
}
else if(e[rot].size() == 1){
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: 100
Accepted
time: 1ms
memory: 3840kb
input:
2 5 0 0 1 5 2 4 0 0 0 0 1 1 2 0 2 0 0 2
output:
? 1 5 ? 2 4 ! 3 ? 1 2 ! 2
result:
ok OK (2 test cases)
Test #2:
score: -100
Runtime Error
input:
5555 8 2 0 8 6 0 0 3 0 0 0 7 0 0 0 5 4 2 0 2 8 0 0 1 4 2 0 0 0 7 8 0 0 3 0 6 0 2 1 0 8 5 8 0 0 1 7 0 0 0 0 4 2 0 0 6 0 2 1 2 5 4 5 3 1 0 0 0 0 0 0 1 2 8 0 0 0 0 5 6 0 0 1 4 2 0 3 8 0 0 0 0 5 3 0 5 1 0 0 0 0 4 0 0 2 5 5 0 0 0 0 0 3 0 2 4 1 0 3 3 0 1 0 0 0 2 2 2 0 0 0 0 3 2 3 0 0 0 0 2 10 2 8 9 7 0 0 ...
output:
? 1 8 ? 4 5 ? 4 3 ! 3 ? 5 3 ? 1 4 ? 3 2 ! 3 ? 5 8 ? 4 2 ? 8 6 ! 6 ? 4 5 ? 1 3 ! 3 ? 5 6 ? 4 1 ! 4 ? 5 1 ? 5 4 ! 4 ? 1 2 ? 5 3 ! 5 ? 3 2 ! 2 ? 1 2 ! 1 ? 2 3 ! 3 ? 1 9 ? 5 6 ? 4 3 ! 3 ? 1 2 ! 1 ? 5 9 ? 4 8 ? 5 3 ! 5 ? 3 10 ? 6 2 ? 10 4 ! 8 ? 3 9 ? 1 7 ? 9 2 ! 9 ? 1 2 ! 2 ? 4 3 ? 7 1 ! 1 ? 6 2 ? 5 9 ? ...