結果

問題 No.2274 三角彩色
ユーザー lam6er
提出日時 2025-03-20 21:13:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 81 ms / 2,000 ms
コード長 2,194 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 82,676 KB
実行使用メモリ 76,760 KB
最終ジャッジ日時 2025-03-20 21:14:46
合計ジャッジ時間 2,293 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    M = int(input[ptr]); ptr +=1
    B = int(input[ptr]); ptr +=1
    Q = int(input[ptr]); ptr +=1
    
    edges = []
    for _ in range(M):
        i = int(input[ptr]); ptr +=1
        j = int(input[ptr]); ptr +=1
        edges.append((i, j))
    
    # Compute u (number of distinct vertices in edges)
    u = set()
    for i, j in edges:
        u.add(i)
        u.add(j)
    u_size = len(u)
    
    # Compute connected components (c_edge) in edge-induced graph
    parent = {}
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # Path compression
            x = parent[x]
        return x
    
    def union(x, y):
        x_root = find(x)
        y_root = find(y)
        if x_root != y_root:
            parent[y_root] = x_root
    
    # Initialize parent for each node in u
    for i, j in edges:
        if i not in parent:
            parent[i] = i
        if j not in parent:
            parent[j] = j
    
    for i, j in edges:
        union(i, j)
    
    components = set()
    for node in parent:
        components.add(find(node))
    c_edge = len(components)
    
    # Compute d
    d = M - (u_size - c_edge)
    
    # Process queries and compute t using Gaussian elimination over GF(2)
    basis = [0] * M  # Basis vectors, represented as integers (bitmask)
    for _ in range(Q):
        m0 = int(input[ptr]); ptr +=1
        m1 = int(input[ptr]); ptr +=1
        m2 = int(input[ptr]); ptr +=1
        vec = (1 << m0) | (1 << m1) | (1 << m2)
        current = vec
        # Reduce current vector
        for i in reversed(range(M)):
            if (current >> i) & 1:
                if basis[i]:
                    current ^= basis[i]
                else:
                    basis[i] = current
                    break
    # Compute rank t (number of non-zero vectors in basis)
    t = sum(1 for v in basis if v != 0)
    
    # Calculate results modulo B
    pow_2d = pow(2, d, B)
    pow_2t = pow(2, t, B)
    S = (pow_2d - pow_2t) % B
    T = pow_2t % B
    
    print(S, T)

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