結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }