結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
![]() |
提出日時 | 2025-08-15 22:49:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 348 ms / 3,000 ms |
コード長 | 3,246 bytes |
コンパイル時間 | 5,783 ms |
コンパイル使用メモリ | 335,276 KB |
実行使用メモリ | 25,844 KB |
平均クエリ数 | 13.74 |
最終ジャッジ日時 | 2025-08-15 22:51:14 |
合計ジャッジ時間 | 14,655 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace atcoder; using namespace std; typedef long long ll; template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); rep(i, 0, n) { os << v[i] << " \n"[i == n - 1]; } return os; } bool ask(vector<int> &q) { cout << "? "; for (int x : q) { cout << x + 1 << " "; } cout << endl; string s; cin >> s; return s == "Yes"; } void answer(int k) { cout << "! " << k + 1 << endl; } void solve() { int n; cin >> n; vector<vector<int>> tr(n); vector<int> u(n), v(n); rep(i, 0, n - 1) { cin >> u[i] >> v[i]; u[i]--, v[i]--; tr[u[i]].push_back(v[i]); tr[v[i]].push_back(u[i]); } vector<int> depth(n, -1); auto dfs = [&](auto self, int x, int p) -> int { depth[x] = p == -1 ? 0 : depth[p] + 1; int res = 0; for (int y : tr[x]) { if (y == p) continue; res += self(self, y, x); } return res + (p == -1 ? 0 : 1); }; dfs(dfs, 0, -1); vector<int> q; rep(i, 0, n - 1) { if (depth[u[i]] & 1) { q.push_back(u[i]); } else { q.push_back(v[i]); } } bool result = ask(q); vector<int> ng(n); auto update_ng = [&](vector<int> &q, bool ask_result) { if (ask_result) { ng = vector<int>(n, 1); for (auto x : q) ng[x] = 0; } else { for (auto x : q) ng[x] = 1; } }; update_ng(q, result); auto make_half = [&]() { int cnt = 0; for (int i = 0; i < n; i++) { if (ng[i] == 0) cnt++; } vector<int> ret; for (int i = 0; i < n && ret.size() < (cnt + 1) / 2; i++) { if (ng[i] == 0) { ret.push_back(i); } } return ret; }; auto calc_zero = [&]() { int ret = 0; for (auto x : ng) ret += x == 0; return ret; }; auto make_query = [&](vector<int> &half) { vector<int> is_half(n); for (auto x : half) is_half[x] = 1; vector<int> q(n - 1, -1); rep(i, 0, n - 1) { if (is_half[u[i]]) { q[i] = u[i]; } if (is_half[v[i]]) { q[i] = v[i]; } } rep(i, 0, n - 1) { if (q[i] != -1) continue; if (ng[u[i]] == 1) { q[i] = u[i]; } if (ng[v[i]] == 1) { q[i] = v[i]; } } rep(i, 0, n - 1) assert(q[i] != -1); return q; }; rep(i, 0, 14) { if (calc_zero() == 1) { rep(i, 0, n) { if (ng[i] == 0) { answer(i); return; } } } auto half = make_half(); auto q = make_query(half); bool ask_result = ask(q); update_ng(half, ask_result); } cout << "WA" << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; while (t--) solve(); }