結果
問題 | No.2319 Friends+ |
ユーザー |
|
提出日時 | 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 |
ソースコード
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] * NFriendData = [[] for _ in range(N)]for a, b in AB:a -= 1b -= 1FriendCnt[a] += 1FriendCnt[b] += 1FriendData[a].append(b)FriendData[b].append(a)Boader = 2000TypeList = [0] * NNotifyList = []FreField = {}for i in range(N):if FriendCnt[i] > Boader:NotifyList.append(i)TypeList[i] = 1FreField[i] = [0] * Nfor j in FriendData[i]:FreField[i][P[j]] += 1FreNoticeList = [[] 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 Falseif TypeList[x]:return FreField[x][yroom] != 0else:for d in FriendData[x]:droom = Eto[d]if droom == yroom:return Truereturn Falsefor x, y in XY:x -= 1y -= 1if nasu(x, y):print("Yes")xroom = Eto[x]yroom = Eto[y]for d in FreNoticeList[x]:FreField[d][xroom] -= 1FreField[d][yroom] += 1Eto[x] = yroomelse:print("No")