QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733117 | #9570. Binary Tree | ucup-team059 | RE | 1ms | 3808kb | C++20 | 3.2kb | 2024-11-10 17:16:45 | 2024-11-10 17:16:47 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
void solve(){
int n;
std::cin >> n;
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n; i++){
int L, R;
std::cin >> L >> R;
L--, R--;
if (R >= 0) {
adj[i].push_back(R);
adj[R].push_back(i);
}
if (L >= 0) {
adj[i].push_back(L);
adj[L].push_back(i);
}
}
std::vector<int> cut(n);
auto work = [&](int root){
std::vector<int> size(n, 1e9), max(n, 1e9);
int tot = 0;
auto dfs = [&](auto &&self, int x, int fa)->void{
size[x] = 1;
max[x] = 0;
tot++;
for (auto y : adj[x]){
if (y == fa || cut[y]) continue;
self(self, y, x);
size[x] += size[y];
max[x] = std::max(max[x], size[y]);
}
};
dfs(dfs, root, -1);
int heavy = root, val = std::max(max[heavy], tot - max[heavy]);
for (int i = 0; i < n; i++){
if (val > std::max(max[i], tot - max[i])){
heavy = i;
val = std::max(max[i], tot - max[i]);
}
}
std::vector<std::pair<int, int>> son;
for (auto y : adj[heavy]){
if (cut[y]) continue;
son.push_back({size[y], y});
}
std::sort(son.begin(), son.end(), std::greater<>());
return std::make_pair(heavy, son);
};
auto query = [](int u, int v){
std::cout << "? " << u + 1 << ' ' << v + 1 << std::endl;
int t;
std::cin >> t;
return t;
};
int root = 0;
while (true){
auto [x, son] = work(root);
int dag = 0;
dag = son.size();
if (dag == 0) {
std::cout << "! ";
std::cout << x + 1 << std::endl;
return;
}else if (dag == 1){
int t = query(x, son[0].second);
if (t == 0){
std::cout << "! ";
std::cout << x + 1 << std::endl;
}else{
std::cout << "! ";
std::cout << son[0].second + 1 << std::endl;
}
return;
}else if (dag == 2){
int t = query(son[0].second, son[1].second);
if (t == 0){
cut[x] = 1;
root = son[0].second;
}else if (t == 1){
std::cout << "! ";
std::cout << x + 1 << std::endl;
return;
}else{
cut[x] = 1;
root = son[1].second;
}
}else if (dag == 3){
int t = query(son[0].second, son[1].second);
if (t == 0){
cut[x] = 1;
root = son[0].second;
}else if (t == 1){
cut[x] = 1;
root = son[2].second;
}else{
cut[x] = 1;
root = son[1].second;
}
}
}
}
int main() {
int t;
std::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: 3808kb
input:
2 5 0 0 1 5 2 4 0 0 0 0 2 0 2 0 2 0 0 2
output:
? 1 3 ? 3 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 2 2 8 5 8 0 0 1 7 0 0 0 0 4 2 0 0 6 0 0 2
output:
? 1 8 ? 4 5 ? 4 3 ! 3 ? 2 7 ? 7 8 ? 8 6 ! 6 ? 8 3 ? 8 6 ! 6