結果
| 問題 | No.2319 Friends+ |
| ユーザー |
 navel_tos
|
| 提出日時 | 2023-05-26 22:49:32 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 2,414 bytes |
| コンパイル時間 | 433 ms |
| コンパイル使用メモリ | 82,048 KB |
| 実行使用メモリ | 852,608 KB |
| 最終ジャッジ日時 | 2024-06-07 08:18:45 |
| 合計ジャッジ時間 | 3,746 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 40 ms
52,096 KB |
| testcase_01 | AC | 39 ms
52,224 KB |
| testcase_02 | MLE | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
ソースコード
#yukicoder390F Friends+
'''
フレンド関係があり、joinコマンドで移動する。
異なるワールドにいて、かつ、移動先にフレンドが一人いるときだけ移動可能。
コマンドの成否を判定しろ。
いまどこ？と友達？を判定しよう。
友達関係はUFを使えばいいか。
友達が特定の場所にいるか？の判定が面倒だな。
これタスク分割ですかね？
友達が多い人は、「いまぼくここだよ」で処理。
友達が少ない人は逐次確認。
カットオフはどれくらいだろう。300人くらい？
前は「ウニグラフで630人くらいがカットオフ」って話があったな。
今回はNが小さくて済むから、200人くらいにしておこうかな。
要件確認。
非vip: 全友達の現在地を逐次確認する。移動先にいれば移動する。
移動後、現在地をvipに送付する。
vip: 非vipの友達の現在地は即座に確認する。
vipの友達の現在地は逐次確認する。
提出デバッグの可能性が高そう。vipの閾値は手動変更できるようにしておこう。
まじかよ、MLEした。ショック。
'''
f=lambda:list(map(int,input().split()))
N,M=f(); P=list(map(lambda x: x-1,f())); G=[[] for _ in range(N)]
for _ in range(M): a,b=f(); G[a-1].append(b-1); G[b-1].append(a-1)
vip_cutoff=300 #カットオフを入力してください
vip=set()
for i in range(N):
if len(G[i])>=vip_cutoff: vip.add(i)
#vip用の、非vipの者どもの所在確認リストを用意する
V=[[0]*N for _ in range(N)]; Comeon=[set() for _ in range(N)]
for vipper in vip:
for next in G[vipper]:
Comeon[next].add(vipper)
if next not in vip: V[vipper][P[next]]+=1 #非vipの人の居場所だけを格納する
for _ in range(int(input())):
x,y=f(); x-=1; y-=1; before=P[x]
if P[x]==P[y]: print('No'); continue
if x not in vip:
for next in G[x]:
if P[next]==P[y]:
P[x]=P[y]; print('Yes')
for vipper in Comeon[x]:
V[vipper][before]-=1; V[vipper][P[x]]+=1
break
else: print('No')
else:
if V[x][P[y]]==0:
for next in Comeon[x]:
if P[next]==P[y]: P[x]=P[y]; print('Yes'); break
else: print('No')
else: P[x]=P[y]; print('Yes')