Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# 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
→ Source
#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 ;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details