結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
![]() |
提出日時 | 2025-08-10 16:07:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 339 ms / 3,000 ms |
コード長 | 1,499 bytes |
コンパイル時間 | 3,454 ms |
コンパイル使用メモリ | 290,088 KB |
実行使用メモリ | 26,212 KB |
平均クエリ数 | 16.00 |
最終ジャッジ日時 | 2025-08-10 16:07:41 |
合計ジャッジ時間 | 11,571 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
#include<bits/stdc++.h> using namespace std; int N; bool query(vector<int> x){ cout << '?'; for(int i : x){ cout << " " << i+1; } cout << endl; string S; cin >> S; assert(S!="Invalid"); return S=="Yes"; } int main(){ cin >> N; vector<vector<int>> G(N); vector<pair<int,int>> E(N-1); for(int i=0;i<N-1;i++){ int u,v; cin >> u >> v; u--; v--; G[u].emplace_back(v); G[v].emplace_back(u); E[i]=make_pair(u,v); } queue<int> que; vector<int> col(N,-1); col[0]=0; que.push(0); while(!que.empty()){ int pos=que.front(); que.pop(); for(int nv : G[pos]){ if(col[nv]!=-1) continue; col[nv]=col[pos]^1; que.push(nv); } } { vector<int> x(N-1); for(int i=0;i<N-1;i++){ //colが0の方にする if(col[E[i].first]==0){ x[i]=E[i].first; } else{ x[i]=E[i].second; } } bool check=query(x); if(!check){ //colを反転させる for(int i=0;i<N;i++){ col[i]^=1; } } } //colが0の方に宝がある vector<int> default_x(N-1); for(int i=0;i<N-1;i++){ if(col[E[i].first]==1){ default_x[i]=E[i].first; } else{ default_x[i]=E[i].second; } } int ans=0; for(int i=0;i<14;i++){ //2^iの位が1になっているcolが1の頂点だけ変更 vector<int> x=default_x; for(int j=0;j<N-1;j++){ int res=E[j].first; if(col[E[j].first]==1){ res=E[j].second; } if(res&(1<<i)){ x[j]=res; } } bool check=query(x); if(check){ ans|=1<<i; } } cout << "! " << ans+1 << endl; }