結果

問題 No.3237 Find the Treasure!
コンテスト
ユーザー yu23578
提出日時 2025-08-15 22:35:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 365 ms / 3,000 ms
コード長 1,939 bytes
コンパイル時間 2,107 ms
コンパイル使用メモリ 212,712 KB
実行使用メモリ 25,972 KB
平均クエリ数 13.83
最終ジャッジ日時 2025-08-15 22:37:27
合計ジャッジ時間 11,607 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long

int N;

signed main(){
  cin>>N;
  if(N == 1){
  	cout << "! 1" << endl;
  	return 0;
  }
  vector<pair<int,int>> edge(N-1);
  vector<vector<int>> G(N);
  for(int i = 0; i < N-1; i++){
  	cin>>edge[i].first>>edge[i].second;
  	edge[i].first--;
  	edge[i].second--;
  	G[edge[i].first].push_back(edge[i].second);
  	G[edge[i].second].push_back(edge[i].first);
  }
  vector<bool> nibu(N);
  vector<bool> visited(N);
  vector<int> kouho;
  //1次予選.
  queue<int> Q; Q.push(0); visited[0] = true;
  while(!Q.empty()){
  	int now = Q.front();
  	Q.pop();
  	for(int i:G[now]){
  		if(visited[i]) continue;
  		visited[i] = true;
  		nibu[i] = 1 - nibu[now];
  		Q.push(i);
  	}
  }
  cout << "? ";
  for(int i = 0; i < N-1; i++){
	if(nibu[edge[i].first]) cout << edge[i].first+1 << " ";
	else cout << edge[i].second+1 << " ";
  }
  cout << endl;
  string H; cin>>H;
  bool p = false;
  if(H == "Yes") p = true;
  for(int i = 0; i < N; i++){
  	if(p == nibu[i]) kouho.push_back(i);
  }
  while((int)kouho.size() > 1){
  	vector<int> Z(N);
  	cout << "? ";
  	int mid = ((int)kouho.size()) / 2;
  	for(int i = 0; i < mid; i++){
  		Z[kouho[i]] = 2;
  	}
  	for(int i = mid; i < (int)(kouho.size()); i++){
  		Z[kouho[i]] = 1;
  	}
  	for(int i = 0; i < N-1; i++){
  		int a = edge[i].first;
  		int b = edge[i].second;
  		if(Z[a] == 2){
  			cout << a+1 << " ";
  		}
  		else if(Z[a] == 1){
  			cout << b+1 << " ";
  		}
  		else if(Z[b] == 1){
  			cout << a+1 << " ";
  		}
  		else if(Z[b] == 2){
  			cout << b+1 << " ";
  		}
  		else{
  			cout << a+1 << " ";
  		}
  	}
  	cout << endl;
  	string res; cin>>res;
  	vector<int> ara;
  	if(res == "Yes"){
  		for(int i = 0; i < mid; i++) ara.push_back(kouho[i]);
  	}
  	else{
  		for(int i = mid; i < (int)kouho.size(); i++) ara.push_back(kouho[i]);
  	}
  	kouho = ara;
  }
  cout << "! " << kouho[0]+1 << endl;
}
0