結果

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

ソースコード

diff # 

from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    P = list(map(int, data[idx:idx+N]))
    idx += N
    current_world = [0] * (N + 1)
    for i in range(N):
        current_world[i+1] = P[i]
    
    friends_adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        A = int(data[idx])
        B = int(data[idx+1])
        friends_adj[A].append(B)
        friends_adj[B].append(A)
        idx += 2
    
    # Initialize friends_in_ws and S
    friends_in_ws = [defaultdict(int) for _ in range(N + 1)]
    S = [set() for _ in range(N + 1)]
    for X in range(1, N + 1):
        for F in friends_adj[X]:
            W = current_world[F]
            friends_in_ws[X][W] += 1
        # Populate S[X]
        for W in friends_in_ws[X]:
            if friends_in_ws[X][W] > 0:
                S[X].add(W)
    
    Q = int(data[idx])
    idx += 1
    
    output = []
    for _ in range(Q):
        X = int(data[idx])
        Y = int(data[idx+1])
        idx += 2
        
        if current_world[X] == current_world[Y]:
            output.append("No")
            continue
        
        WY = current_world[Y]
        if WY in S[X]:
            output.append("Yes")
            old_world = current_world[X]
            current_world[X] = WY
            
            for F in friends_adj[X]:
                # Process old world
                old_count = friends_in_ws[F].get(old_world, 0)
                if old_count > 0:
                    new_count_old = old_count - 1
                    friends_in_ws[F][old_world] = new_count_old
                    if new_count_old == 0:
                        S[F].discard(old_world)
                # Process new world
                new_count = friends_in_ws[F].get(WY, 0)
                friends_in_ws[F][WY] = new_count + 1
                if new_count == 0:
                    S[F].add(WY)
        else:
            output.append("No")
    
    print('\n'.join(output))

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