結果

問題 No.3237 Find the Treasure!
コンテスト
ユーザー hirayuu_yc
提出日時 2025-08-10 15:32:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 409 ms / 3,000 ms
コード長 1,127 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 96,868 KB
平均クエリ数 13.83
最終ジャッジ日時 2025-08-10 15:43:01
合計ジャッジ時間 10,256 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N=int(input())
tree=[[] for i in range(N)]
edge=[]
for i in range(N-1):
    u,v=map(int,input().split())
    edge.append((u,v))
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)
dist=[-1]*N
vert=[0]
dist[0]=0
while vert:
    pos=vert.pop()
    for i in tree[pos]:
        if dist[i]==-1:
            dist[i]=dist[pos]+1
            vert.append(i)
x=[0]*(N-1)
for i in range(N-1):
    if dist[edge[i][0]-1]%2==0:
        x[i]=edge[i][0]
    else:
        x[i]=edge[i][1]
print("?",*x)
res=input()
cand=[]
if res=="Yes":
    for i in range(N):
        if dist[i]%2==0:
            cand.append(i)
else:
    for i in range(N):
        if dist[i]%2==1:
            cand.append(i)
while len(cand)>1:
    mid=len(cand)//2
    memo=[0]*N
    for i in range(mid):
        memo[cand[i]]=1
    for i in range(mid,len(cand)):
        memo[cand[i]]=-1
    for i in range(N-1):
        if memo[edge[i][0]-1]==1 or memo[edge[i][1]-1]==-1:
            x[i]=edge[i][0]
        else:
            x[i]=edge[i][1]
    print("?",*x)
    res=input()
    if res=="Yes":
        cand=cand[:mid]
    else:
        cand=cand[mid:]
print("!",cand[0]+1)
0