結果

問題 No.2319 Friends+
コンテスト
ユーザー detteiuu
提出日時 2026-07-20 21:34:51
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 420 ms / 3,000 ms
+ 494µs
コード長 1,767 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 231 ms
コンパイル使用メモリ 96,208 KB
実行使用メモリ 138,532 KB
最終ジャッジ日時 2026-07-20 21:35:09
合計ジャッジ時間 17,527 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from sys import stdin
input = stdin.readline
from collections import defaultdict

shikii = 2000

def encode(a, b):
    return a<<20|b

N, M = map(int, input().split())
P = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]

# from random import randrange
# N = 20000
# M = 200000
# P = [randrange(1, N+1) for _ in range(N)]
# AB = []
# S = set()
# while len(AB) < M:
#     A, B = randrange(1, N+1), randrange(1, N+1)
#     if A > B: A, B = B, A
#     if A == B: continue
#     if (A, B) in S: continue
#     AB.append((A, B))
#     S.add((A, B))
# Q = 200000
# query = []
# S = set()
# while len(query) < Q:
#     X, Y = randrange(1, N+1), randrange(1, N+1)
#     if X == Y: continue
#     if (X, Y) in S: continue
#     query.append((X, Y))
#     S.add((X, Y))

P = [p-1 for p in P]

G = [[] for _ in range(N)]
for A, B in AB:
    A, B = A-1, B-1
    G[A].append(B)
    G[B].append(A)

big = [False]*N
for i in range(N):
    big[i] = shikii <= len(G[i])

GB = [[] for _ in range(N)]
for n in range(N):
    for v in G[n]:
        if big[v]:
            GB[n].append(v)

D = defaultdict(int)
for n in range(N):
    if not big[n]: continue
    for v in G[n]:
        D[encode(n, P[v])] += 1

for X, Y in query:
    X, Y = X-1, Y-1
    Y = P[Y]
    if P[X] == Y:
        print("No")
        continue
    pre = P[X]
    if big[X]:
        if 1 <= D[encode(X, Y)]:
            P[X] = Y
    else:
        for v in G[X]:
            if P[v] == Y:
                P[X] = Y
                break
    
    if P[X] == Y:
        print("Yes")
        for v in GB[X]:
            D[encode(v, pre)] -= 1
            D[encode(v, Y)] += 1
    else:
        print("No")
0