結果

問題 No.2319 Friends+
ユーザー lam6er
提出日時 2025-04-15 21:31:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,760 ms / 3,000 ms
コード長 1,287 bytes
コンパイル時間 494 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 410,736 KB
最終ジャッジ日時 2025-04-15 21:35:27
合計ジャッジ時間 76,178 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N, M = int(data[idx]), int(data[idx+1])
    idx +=2
    
    pos = list(map(int, data[idx:idx+N]))
    idx +=N
    pos = [0] + pos  # 1-based index
    
    current_bitmask = [0] * (N + 1)  # worlds are 1-based
    for i in range(1, N+1):
        w = pos[i]
        current_bitmask[w] |= 1 << (i-1)
    
    friend_bitmask = [0] * (N + 1)
    for _ in range(M):
        A = int(data[idx])
        B = int(data[idx+1])
        idx +=2
        friend_bitmask[A] |= 1 << (B-1)
        friend_bitmask[B] |= 1 << (A-1)
    
    Q = int(data[idx])
    idx +=1
    output = []
    for _ in range(Q):
        X = int(data[idx])
        Y = int(data[idx+1])
        idx +=2
        if pos[X] == pos[Y]:
            output.append("No")
            continue
        target_w = pos[Y]
        if (friend_bitmask[X] & current_bitmask[target_w]) != 0:
            output.append("Yes")
            old_w = pos[X]
            # Update current_bitmask
            current_bitmask[old_w] &= ~ (1 << (X-1))
            current_bitmask[target_w] |= (1 << (X-1))
            pos[X] = target_w
        else:
            output.append("No")
    
    print('\n'.join(output))

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