結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
|
提出日時 | 2025-08-24 07:29:53 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 492 ms / 3,000 ms |
コード長 | 1,701 bytes |
コンパイル時間 | 318 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 32,640 KB |
平均クエリ数 | 14.00 |
最終ジャッジ日時 | 2025-08-24 07:30:06 |
合計ジャッジ時間 | 13,080 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
# -*- coding: utf-8 -*- """ Created on Sat Aug 23 23:04:27 2025 @author: Tekyla """ N = int(input()) path = [list(map(int, input().split())) for _ in range(N-1)] path_tmp = [[] for _ in range(N+1)] for u,v in path: path_tmp[u].append(v) path_tmp[v].append(u) depth = [-1] * (N+1) st = [1] depth[1] = 0 while st: u = st.pop() for v in path_tmp[u]: if depth[v] < 0: depth[v] = depth[u]^1 st.append(v) # 初手の質問 # 奇数をクエリに投げる x = [path[i][0] if depth[path[i][0]]%2==1 else path[i][1] for i in range(N-1)] print("?", *x) S = input() ng = set(x) if S == "Yes": ng = set([i for i in range(1, N+1)]) - ng # ここから繰り返す while len(ng) < N-1: q_set = set() nq_set = set() x = [] for u,v in path: if u in q_set: x.append(u) elif v in q_set: x.append(v) elif u in nq_set: x.append(v) elif v in nq_set: x.append(u) elif u in ng: if v in ng: x.append(u) else: if len(q_set) < len(nq_set): q_set.add(v) x.append(v) else: nq_set.add(v) x.append(u) else: if len(q_set) < len(nq_set): q_set.add(u) x.append(u) else: nq_set.add(u) x.append(v) print("?", *x) S = input() if S == "Yes": ng.update(nq_set) else: ng.update(q_set) # こたえ ans = -1 for i in range(1, N+1): if i not in ng: ans = i print("!", ans)