結果

問題 No.3237 Find the Treasure!
コンテスト
ユーザー ゼット
提出日時 2025-08-15 22:05:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 467 ms / 3,000 ms
コード長 1,316 bytes
コンパイル時間 332 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 97,784 KB
平均クエリ数 13.96
最終ジャッジ日時 2025-08-15 22:05:40
合計ジャッジ時間 11,704 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

N=int(input())
G=[[] for i in range(N)]
L=[]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  L.append((a,b))
dist=[-1]*N
from collections import deque
S=deque()
dist[0]=0
S.append(0)
while S:
  x=S.pop()
  for y in G[x]:
    if dist[y]>=0:
      continue
    dist[y]=dist[x]+1
    S.append(y)
h=[]
for i in range(N-1):
  a,b=L[i][:]
  if dist[a-1]%2==0:
    h.append(a)
  else:
    h.append(b)
print('?',*h,flush=True)
ans=input()
rest=[True]*N
if ans=='Yes':
  for i in range(N):
    if dist[i]%2==1:
      rest[i]=False
else:
  for i in range(N):
    if dist[i]%2==0:
      rest[i]=False
while True:
  p=[]
  for i in range(N):
    if rest[i]==True:
      p.append(i)
  if len(p)==1:
    x=p[0]+1
    print('!',x,flush=True)
    exit()
  used=[True]*N
  h=[]
  for i in range(len(p)):
    if i%2==1:
      used[p[i]]=False
  for i in range(N-1):
    a,b=L[i][:]
    if rest[a-1]==True:
      if used[a-1]==False:
        h.append(b)
      else:
        h.append(a)
    else:
      if used[b-1]==False:
        h.append(a)
      else:
        h.append(b)
  print('?',*h,flush=True)
  ans=input()
  if ans=='Yes':
    for i in range(len(p)):
      if i%2==1:
        rest[p[i]]=False
  else:
    for i in range(len(p)):
      if i%2==0:
        rest[p[i]]=False
0