結果

問題 No.2319 Friends+
ユーザー D.F.ナス太郎D.F.ナス太郎
提出日時 2024-11-10 22:25:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 719 ms / 3,000 ms
コード長 1,334 bytes
コンパイル時間 391 ms
コンパイル使用メモリ 81,636 KB
実行使用メモリ 129,064 KB
最終ジャッジ日時 2024-11-10 22:26:29
合計ジャッジ時間 23,895 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

N, M = list(map(int, input().split()))
P = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
XY = [list(map(int, input().split())) for _ in range(Q)]
P = [P[i] - 1 for i in range(N)]
FriendCnt = [0] * N
FriendData = [[] for _ in range(N)]
for a, b in AB:
a -= 1
b -= 1
FriendCnt[a] += 1
FriendCnt[b] += 1
FriendData[a].append(b)
FriendData[b].append(a)
Boader = 2000
TypeList = [0] * N
NotifyList = []
FreField = {}
for i in range(N):
if FriendCnt[i] > Boader:
NotifyList.append(i)
TypeList[i] = 1
FreField[i] = [0] * N
for j in FriendData[i]:
FreField[i][P[j]] += 1
FreNoticeList = [[] for _ in range(N)]
for i in range(N):
for d in FriendData[i]:
if TypeList[d]:
FreNoticeList[i].append(d)
Eto = [P[i] for i in range(N)]
def nasu(x, y):
xroom = Eto[x]
yroom = Eto[y]
if xroom == yroom: return False
if TypeList[x]:
return FreField[x][yroom] != 0
else:
for d in FriendData[x]:
droom = Eto[d]
if droom == yroom:
return True
return False
for x, y in XY:
x -= 1
y -= 1
if nasu(x, y):
print("Yes")
xroom = Eto[x]
yroom = Eto[y]
for d in FreNoticeList[x]:
FreField[d][xroom] -= 1
FreField[d][yroom] += 1
Eto[x] = yroom
else:
print("No")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0