結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
![]() |
提出日時 | 2025-08-15 22:46:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 398 ms / 3,000 ms |
コード長 | 3,019 bytes |
コンパイル時間 | 3,669 ms |
コンパイル使用メモリ | 292,652 KB |
実行使用メモリ | 26,228 KB |
平均クエリ数 | 13.83 |
最終ジャッジ日時 | 2025-08-15 22:46:57 |
合計ジャッジ時間 | 12,906 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define ll long long const long long mod=998244353; const long long hmod=46216567629137; int main(){ cin.tie(0)->sync_with_stdio(0); cout.tie(0); int N; cin>>N; int u[N],v[N]; vector<pair<int,int>>G[N+1]; for(int i=1;i<=N-1;i++){ cin>>u[i]>>v[i]; G[u[i]].push_back({v[i],i}); G[v[i]].push_back({u[i],i}); } int dist[N+1]; bool already[N+1]; for(int i=1;i<=N;i++){ dist[i]=0; already[i]=0; } function<void(int)>dfs=[&](int pos){ already[pos]=1; for(int i=0;i<G[pos].size();i++){ int nex=G[pos][i].first; if(already[nex]) continue; dist[nex]=dist[pos]+1; dfs(nex); } already[pos]=0; return; }; dfs(1); set<int>node; set<int>yet; for(int i=1;i<=N;i++){ if(dist[i]%2==0){ node.insert(i); yet.insert(i); } } cout<<"? "; for(int i=1;i<=N-1;i++){ if(node.count(u[i])&&node.count(v[i])){ if(yet.count(u[i])){ cout<<u[i]<<" "; yet.erase(u[i]); } else{ cout<<v[i]<<" "; yet.erase(v[i]); } } else if(node.count(u[i])){ cout<<u[i]<<" "; yet.erase(u[i]); } else if(node.count(v[i])){ cout<<v[i]<<" "; yet.erase(v[i]); } } cout<<endl; string first_res; cin>>first_res; vector<int>nokori; if(first_res=="Yes"){ for(int i=1;i<=N;i++){ if(node.count(i)) nokori.push_back(i); } } else{ for(int i=1;i<=N;i++){ if(!node.count(i)) nokori.push_back(i); } } int free[N+1]; while(nokori.size()>=2){ yet.clear(); for(int i=1;i<=N;i++) free[i]=-1; rep(i,nokori.size()) free[nokori[i]]=0; for(int i=0;i<nokori.size()/2;i++){ free[nokori[i]]=1; yet.insert(nokori[i]); } cout<<"? "; for(int i=1;i<=N-1;i++){ if(yet.count(u[i])){ cout<<u[i]<<" "; yet.erase(u[i]); } else if(yet.count(v[i])){ cout<<v[i]<<" "; yet.erase(v[i]); } else if(free[u[i]]!=0){ cout<<u[i]<<" "; } else{ cout<<v[i]<<" "; } } cout<<endl; string res; cin>>res; if(res=="Yes"){ nokori.clear(); for(int i=1;i<=N;i++){ if(free[i]==1) nokori.push_back(i); } } else{ nokori.clear(); for(int i=1;i<=N;i++){ if(free[i]==0) nokori.push_back(i); } } } cout<<"! "<<nokori[0]<<endl; }