結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
![]() |
提出日時 | 2025-08-16 14:34:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 368 ms / 3,000 ms |
コード長 | 1,930 bytes |
コンパイル時間 | 532 ms |
コンパイル使用メモリ | 61,668 KB |
実行使用メモリ | 25,972 KB |
平均クエリ数 | 14.43 |
最終ジャッジ日時 | 2025-08-16 14:34:17 |
合計ジャッジ時間 | 9,930 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
コンパイルメッセージ
main.cpp: In function ‘bool query(int, int*)’: main.cpp:38:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 38 | scanf("%s", s); | ~~~~~^~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:51:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 51 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:55:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 55 | scanf("%d%d", &u, &v); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 3237.cc: No.3237 Find the Treasure! - yukicoder */ #include<cstdio> #include<vector> #include<algorithm> #include<utility> using namespace std; /* constant */ const int MAX_N = 10000; /* typedef */ using vi = vector<int>; using pii = pair<int,int>; /* global variables */ vi nbrs[MAX_N]; pii es[MAX_N]; int ps[MAX_N], cis[MAX_N], ds[MAX_N]; int xs[MAX_N]; bool used[MAX_N]; /* subroutines */ bool query(int m, int xs[]) { putchar('?'); for (int i = 0; i < m; i++) printf(" %d", xs[i] + 1); putchar('\n'); fflush(stdout); char s[16]; scanf("%s", s); if (s[0] == 'I') exit(0); return (s[0] == 'Y'); } void answer(int t) { printf("! %d\n", t + 1); fflush(stdout); } /* main */ int main() { int n; scanf("%d", &n); int m = n - 1; for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; nbrs[u].push_back(v); nbrs[v].push_back(u); es[i] = {u, v}; } ps[0] = -1, ds[0] = 0; vi gvs[2]; gvs[0].push_back(0); for (int u = 0; u >= 0;) { auto &nbru = nbrs[u]; int up = ps[u]; if (cis[u] < nbru.size()) { int v = nbru[cis[u]++]; if (v != up) { ps[v] = u, ds[v] = ds[u] ^ 1; gvs[ds[v]].push_back(v); u = v; } } else { u = up; } } for (int i = 0; i < m; i++) { auto [u, v] = es[i]; xs[i] = (! ds[u]) ? u : v; } int gid = query(m, xs) ? 0 : 1; auto &gv = gvs[gid]; int k = gv.size(); for (int i = 0; i < m; i++) { auto &[u, v] = es[i]; if (ds[u] != gid) swap(u, v); } int bits = 0; for (int bi = 1; bi < k; bi <<= 1) { fill(used, used + n, false); for (int i = 0; i < k; i++) if (i & bi) used[gv[i]] = true; for (int i = 0; i < m; i++) { auto [u, v] = es[i]; xs[i] = used[u] ? u : v; } if (query(m, xs)) bits |= bi; } answer(gv[bits]); //for (int i = 0; i < 1e9; i++); return 0; }