結果

問題 No.2319 Friends+
ユーザー lam6er
提出日時 2025-03-31 17:23:37
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,683 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 55,296 KB
最終ジャッジ日時 2025-03-31 17:24:08
合計ジャッジ時間 8,069 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, M = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    
    pos = list(map(int, input[ptr:ptr+N]))
    ptr += N
    pos = [0] + pos  # 1-based indexing
    
    friends = [[] for _ in range(N+1)]  # friends[1], ..., friends[N]
    for _ in range(M):
        a = int(input[ptr])
        b = int(input[ptr+1])
        ptr +=2
        friends[a].append(b)
        friends[b].append(a)
    
    # Initialize friend_count
    friend_count = [defaultdict(int) for _ in range(N+1)]  # friend_count[x][w] = number of x's friends in w
    for x in range(1, N+1):
        for f in friends[x]:
            w = pos[f]
            friend_count[x][w] += 1
    
    Q = int(input[ptr])
    ptr +=1
    
    for _ in range(Q):
        X = int(input[ptr])
        Y = int(input[ptr+1])
        ptr +=2
        
        x_pos = pos[X]
        y_pos = pos[Y]
        
        if x_pos == y_pos:
            print("No")
            continue
        
        if friend_count[X].get(y_pos, 0) > 0:
            print("Yes")
            old_w = x_pos
            new_w = y_pos
            pos[X] = new_w
            
            # Update friend_count for all friends of X
            for f in friends[X]:
                # Decrement old_w
                if friend_count[f][old_w] > 0:
                    friend_count[f][old_w] -= 1
                    if friend_count[f][old_w] == 0:
                        del friend_count[f][old_w]
                # Increment new_w
                friend_count[f][new_w] += 1
        else:
            print("No")

if __name__ == "__main__":
    main()
0