結果

問題 No.2319 Friends+
コンテスト
ユーザー detteiuu
提出日時 2026-07-20 21:16:08
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,220 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 241 ms
コンパイル使用メモリ 96,240 KB
実行使用メモリ 490,560 KB
最終ジャッジ日時 2026-07-20 21:16:33
合計ジャッジ時間 5,924 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

shikii = 140

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)]

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")
    else:
        print("No")
    
    for v in GB[X]:
        D[encode(v, pre)] -= 1
        D[encode(v, Y)] += 1
0