結果

問題 No.3237 Find the Treasure!
コンテスト
ユーザー Tekyla
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

# -*- 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)
0