結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
![]() |
提出日時 | 2025-08-30 18:06:08 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 361 ms / 3,000 ms |
コード長 | 1,438 bytes |
コンパイル時間 | 1,448 ms |
コンパイル使用メモリ | 111,628 KB |
実行使用メモリ | 26,072 KB |
平均クエリ数 | 13.83 |
最終ジャッジ日時 | 2025-08-30 18:06:20 |
合計ジャッジ時間 | 11,221 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
#include<iostream> #include<queue> #include<vector> #include<numeric> #include<cassert> using namespace std; int main(){ int n; cin>>n; vector<vector<int>>g(n); vector<pair<int,int>>edge(n-1); for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; u--,v--; edge[i]={u,v}; g[u].push_back(v); g[v].push_back(u); } vector<int>dst(n,1e9); dst[0]=0; queue<int>que; que.push(0); while(!que.empty()){ int x=que.front(); que.pop(); for(int i:g[x]){ if(dst[i]>dst[x]+1){ dst[i]=dst[x]+1; que.push(i); } } } auto query=[&](vector<int>x)->bool { cout<<"?"; for(int i:x)cout<<' '<<i+1; cout<<endl; string res; cin>>res; assert(res!="Invalid"); return res=="Yes"; }; vector<int>L,R; auto contain_L=[&]()->bool { vector<int>s(n,-1); for(int l:L)s[l]=0; for(int r:R)s[r]=1; vector<int>x(n-1); for(int i=0;i<n-1;i++){ auto [u,v]=edge[i]; x[i]=u; if(s[u]==0)x[i]=u; if(s[u]==1)x[i]=v; if(s[v]==0)x[i]=v; if(s[v]==1)x[i]=u; } return query(x); }; for(int i=0;i<n;i++){ if(dst[i]%2==0)L.push_back(i); else R.push_back(i); } if(!contain_L())swap(L,R); while(ssize(L)>1){ R.clear(); int sz=ssize(L); R=vector<int>(L.begin()+sz/2,L.end()); L=vector<int>(L.begin(),L.begin()+sz/2); if(!contain_L())swap(L,R); } cout<<"! "<<L[0]+1<<endl; }