QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #766299 | #9570. Binary Tree | XingKongC# | TL | 1ms | 3560kb | C++20 | 1.8kb | 2024-11-20 16:53:34 | 2024-11-20 16:53:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(x) for(ll i = 1; i <= x; i ++)
void solve(){
ll n;
cin >> n;
vector<ll> edge[n + 1];
vector<ll> ind(n + 1);
f(n){
ll u, v;
cin >> u >> v;
if(u != 0)
edge[i].push_back(u);
if(v != 0)
edge[i].push_back(v);
ind[u]++;
ind[v]++;
}
f(n){
if(ind[i] == 0){
ll x = i ;
while(1){
if(edge[x].size() == 0) {
cout << "! " << x << endl;
return ;
}
if(edge[x].size() == 1){
cout << "? " << edge[x][0] << ' ' << x << endl;
ll q;
cin >> q;
if(q == 0){
x = edge[x][0];
}
else {
cout << "! " << x << endl;
return ;
}
}
else {
cout << "? " << edge[x][0] << ' ' << edge[x][1] << endl;
ll q;
cin >> q;
if(q == 0){
x = edge[x][0];
}
else if(q == 1){
cout << "! " << x << endl;
return ;
}
else {
x = edge[x][1];
}
}
}
}
}
}
int main (){
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while(t--) {
solve();
}
return 0;
}
//nanjingnanjing
//4 1 15 -> n 2
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3560kb
input:
2 5 0 0 1 5 2 4 0 0 0 0 0 1 2 0 2 0 0 2
output:
? 2 4 ? 1 5 ! 2 ? 2 1 ! 1
result:
ok OK (2 test cases)
Test #2:
score: -100
Time Limit Exceeded
input:
5555 8 2 0 8 6 0 0 3 0 0 0 7 0 0 0 5 4 0 0 2
output:
? 2 1 ? 8 6 ? 5 4 ? 3 4