# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
72420055 |
Practice:
Dsxv |
1305D
- 26
|
C++17 (GCC 7-32)
|
Wrong answer on test 13
|
31 ms
|
212 KB
|
2020-03-04 17:11:17 |
2020-03-04 17:11:17 |
|
#include <bits/stdc++.h>
using namespace std ;
#define int long long
const int N = 1e3 + 10 ;
set<int> leaves ;
vector<int> G[N] ;
bool done[N] ;
void dfs(int start , int parent){
if(done[start]) return ;
done[start] = 1 ;
if(G[start].size() == 1){
leaves.erase(start) ;
return ;
}
for(auto i : G[start]){
if(i != parent){
dfs(i,start) ;
}
}
}
bool check(int x , int start , int parent){
if(done[start]) return false ;
if(start == x) return true ;
for(auto i : G[start]){
if(i != parent) {
if(check(x,i,start)) return true ;
}
}
return false ;
}
void solve(int lca , int x , int y){
for(auto i : G[lca]){
if(check(x,i,lca) || check(y,i,lca)) {
dfs(i,lca) ;
}
}
}
int32_t main(){
int n ;
cin >> n ;
for(int i = 0 ; i < n - 1 ; i++){
int f ,s ;
cin >> f >> s ;
f-- , s-- ;
G[f].push_back(s) ;
G[s].push_back(f) ;
}
int count = 0 ;
for(int i = 0 ; i < n ; i++){
if(G[i].size() == 1) leaves.insert(i) ;
}
int x , y = *(leaves.rbegin()) ;
int ans = -1 ;
while((int)leaves.size()){
x = *(leaves.begin()) ;
cout << "? "<< x+1 << " " << y+1 << endl ;
count++ ;
int lca ;
cin >> lca ;
lca-- ;
if(lca == x) {
ans = x ;
break ;
}
if(lca == y) {
ans = y ;
break ;
}
solve(lca,x,y) ;
leaves.erase(x) ;
leaves.erase(y) ;
y = lca ;
}
if(count > n/2){
return -1 ;
}
if(ans == -1){
ans = y ;
}
cout <<"! "<< ans+1 << endl ;
return 0 ;
}
Click to see test details