結果
問題 | No.2319 Friends+ |
ユーザー |
👑 ![]() |
提出日時 | 2023-03-14 19:29:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 878 ms / 3,000 ms |
コード長 | 1,655 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 187,008 KB |
最終ジャッジ日時 | 2024-09-18 09:44:54 |
合計ジャッジ時間 | 19,584 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
import sys import math input = sys.stdin.readline #sys.setrecursionlimit(10000000) def read_values(): return map(int, input().split()) def read_index(): return map(lambda x: int(x) - 1, input().split()) def read_list(): return list(read_values()) def read_lists(N): return [read_list() for _ in range(N)] def main(): N,M=read_values() P=read_list() for i in range(N): P[i]-=1 C=[0]*N A=[0]*M B=[0]*M sM = M**0.5 for i in range(M): A[i],B[i]=read_values() A[i]-=1 B[i]-=1 C[A[i]]+=1 C[B[i]]+=1 MG = [[] for _ in range(N)] FG = [[] for _ in range(N)] for i in range(M): if C[B[i]]<sM: FG[A[i]].append(B[i]) else: MG[A[i]].append(B[i]) if C[A[i]]<sM: FG[B[i]].append(A[i]) else: MG[B[i]].append(A[i]) FCnt=[[] for _ in range(N)] for i in range(N): if C[i]>=sM: FCnt[i]=[0]*N for v in FG[i]: FCnt[i][P[v]]+=1 Q = int(input()) for _ in range(Q): X,Y=read_index() if P[X]==P[Y]: print("No") continue cnt=0 for v in MG[X]: cnt+=P[v]==P[Y] if C[X]<sM: for v in FG[X]: cnt+=P[v]==P[Y] else: cnt+=FCnt[X][P[Y]] if cnt: print("Yes") if C[X]<sM: for v in MG[X]: FCnt[v][P[X]]-=1 FCnt[v][P[Y]]+=1 P[X]=P[Y] else: print("No") if __name__ == "__main__": main()