結果
問題 |
No.3237 Find the Treasure!
|
ユーザー |
|
提出日時 | 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 |
ソースコード
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)