結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
![]() |
提出日時 | 2025-08-30 01:50:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 476 ms / 3,000 ms |
コード長 | 1,254 bytes |
コンパイル時間 | 368 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 97,468 KB |
平均クエリ数 | 13.83 |
最終ジャッジ日時 | 2025-08-30 01:50:37 |
合計ジャッジ時間 | 12,636 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
import sys input = sys.stdin.readline N=int(input()) EDGE=[list(map(int,input().split())) for i in range(N-1)] E=[[] for i in range(N+1)] for x,y in EDGE: E[x].append(y) E[y].append(x) X=[-1]*(N+1) X[1]=0 Q=[1] while Q: x=Q.pop() for to in E[x]: if X[to]==-1: X[to]=X[x]^1 Q.append(to) LIST=[] for i in range(1,N+1): if X[i]==0: LIST.append(i) SET=set(LIST) Q=[] for i in range(N-1): x,y=EDGE[i] if x in SET: Q.append(x) else: Q.append(y) print("?",*Q,flush=True) ret=input().strip() if ret=="Yes": pass else: LIST=[] for i in range(1,N+1): if X[i]==1: LIST.append(i) while len(LIST)>1: LIST2=LIST[:len(LIST)//2] SET=set(LIST2) SET2=set(LIST[len(LIST)//2:]) Q=[] for i in range(N-1): x,y=EDGE[i] if x in SET: Q.append(x) elif y in SET: Q.append(y) elif x in SET2: Q.append(y) elif y in SET2: Q.append(x) else: Q.append(y) print("?",*Q,flush=True) ret=input().strip() if ret=="Yes": LIST=LIST2 else: LIST=LIST[len(LIST)//2:] print("!",LIST[0],flush=True)