結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
![]() |
提出日時 | 2025-08-15 21:58:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 351 ms / 3,000 ms |
コード長 | 2,853 bytes |
コンパイル時間 | 5,849 ms |
コンパイル使用メモリ | 335,992 KB |
実行使用メモリ | 25,972 KB |
平均クエリ数 | 13.83 |
最終ジャッジ日時 | 2025-08-15 22:00:03 |
合計ジャッジ時間 | 14,627 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using mint = atcoder::modint998244353; #define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++) #define ll long long #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define siz(x) (int)(x).size() template<class T> bool chmin(T& a, T b) { if (a > b) {a = b; return true;} return false; } template<class T> bool chmax(T& a, T b) { if (a < b) {a = b; return true;} return false; } const int inf = 1e9; const ll INF = 4e18; template<class T> using pq = priority_queue<T, vector<T>, less<T>>; template<class T> using spq = priority_queue<T, vector<T>, greater<T>>; vector<int> di = {0, 0, 1, -1}; vector<int> dj = {1, -1, 0, 0}; struct Edge { int to; ll cost; }; //BFS //重みなしグラフにおける最短経路問題 vector<int> BFS(const vector<vector<int>> &G, int start, int impossible) { queue<int> Q; vector<int> dist((int)G.size(), impossible); Q.push(start); dist[start] = 0; while(!Q.empty()) { int pos = Q.front(); Q.pop(); for (int to : G[pos]) { if (dist[to]!=impossible) continue; Q.push(to); dist[to] = dist[pos]+1; } } return dist; } void solve() { int N; cin >> N; vector<vector<int>> G(N); vector<int> U(N-1), V(N-1); rep(i, 0, N-1) { cin >> U[i] >> V[i]; U[i]--; V[i]--; G[U[i]].push_back(V[i]); G[V[i]].push_back(U[i]); } vector<int> dist = BFS(G, 0, -1); //二部グラフで黒にあるのか白にあるのかを探す cout << "? "; rep(i, 0, N-1) { if (dist[U[i]]%2) cout << U[i]+1; else cout << V[i]+1; cout << " "; } cout << endl; string res; cin >> res; vector<int> now; int choose = (res == "Yes"? 1 : 0); rep(i, 0, N) if (dist[i]%2 == choose) now.push_back(i); //あとは普通に while(siz(now) > 1) { vector<bool> c(N, false); rep(i, 0, siz(now)/2) { c[now[i]] = true; } cout << "? "; rep(i, 0, N-1) { if (c[U[i]]) cout << U[i]+1 << " "; else if (c[V[i]]) cout << V[i]+1 << " "; else { if (dist[U[i]]%2 != choose) cout << U[i]+1 << " "; else cout << V[i]+1 << " "; } assert(!c[U[i]] || !c[V[i]]); } cout << endl; string res; cin >> res; vector<int> nex; if (res == "Yes") { rep(i, 0, siz(now)/2) nex.push_back(now[i]); } else { rep(i, siz(now)/2, siz(now)) nex.push_back(now[i]); } swap(now, nex); } cout << "! "; cout << now[0]+1 << endl; } int main() { int T = 1; while(T--) { solve(); } }