結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
![]() |
提出日時 | 2025-08-15 23:12:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 382 ms / 3,000 ms |
コード長 | 1,185 bytes |
コンパイル時間 | 226 ms |
コンパイル使用メモリ | 82,416 KB |
実行使用メモリ | 97,112 KB |
平均クエリ数 | 13.83 |
最終ジャッジ日時 | 2025-08-15 23:12:41 |
合計ジャッジ時間 | 9,975 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
from collections import deque def question(X): print("?", *[x+1 for x in X]) return input() def answer(n): print("!", n+1) N = int(input()) G = [[] for _ in range(N)] edge = [] for _ in range(N-1): u, v = map(int, input().split()) u, v = u-1, v-1 edge.append((u, v)) G[u].append(v) G[v].append(u) que = deque() que.append(0) color = [-1]*N color[0] = 0 while que: n = que.popleft() for v in G[n]: if color[v] == -1: color[v] = color[n]^1 que.append(v) C = -1 A = [] for u, v in edge: if color[u] == 0: A.append(u) else: A.append(v) ans = question(A) if ans == "Yes": C = 0 else: C = 1 IDX = [i for i in range(N) if color[i] == C] left = 0 right = len(IDX) while left+1 < right: mid = (left+right)//2 A = [] S = set(IDX[left:mid]) for u, v in edge: if u in S: A.append(u) continue if v in S: A.append(v) continue if color[u] == C: A.append(v) else: A.append(u) if question(A) == "No": left = mid else: right = mid answer(IDX[left])