結果

問題 No.1773 Love Triangle
ユーザー hitonanode
提出日時 2021-10-13 23:43:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 647 ms / 2,000 ms
コード長 1,462 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 81,800 KB
最終ジャッジ日時 2024-07-03 21:05:19
合計ジャッジ時間 35,548 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 90
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
import random

random.seed(530629)

md = (1 << 30) + 3  # prime


def modinv(a: int) -> int:
    x = a
    for _ in range(30):
        x = x * x % md
    return x * a % md


def rank_of_matrix(mat):
    n = len(mat)
    rank = 0
    for i in range(n):
        ti = i
        while ti < n and mat[ti][i] == 0:
            ti += 1
        if ti == n:
            continue
        rank += 1
        mat[i], mat[ti] = mat[ti], mat[i]
        mati = mat[i]
        inv = modinv(mati[i])
        for j in range(i + 1, n):
            mati[j] = mati[j] * inv % md
        for h in range(n):
            if i == h:
                continue
            math = mat[h]
            c = md - math[i]
            for j in range(i + 1, n):
                math[j] = (math[j] + mati[j] * c) % md
    return rank


N, M = map(int, input().split())
uvws = [tuple(map(int, input().split())) for _ in range(M)]


def solve() -> int:

    mat = [[0] * N for _ in range(N)]

    for u, v, w in uvws:
        x = random.randrange(0, md)
        mat[u - 1][v - 1] = (mat[u - 1][v - 1] + x) % md
        mat[v - 1][w - 1] = (mat[v - 1][w - 1] + x) % md
        mat[w - 1][u - 1] = (mat[w - 1][u - 1] + x) % md
        mat[v - 1][u - 1] = (mat[v - 1][u - 1] + md - x) % md
        mat[w - 1][v - 1] = (mat[w - 1][v - 1] + md - x) % md
        mat[u - 1][w - 1] = (mat[u - 1][w - 1] + md - x) % md

    return rank_of_matrix(mat) // 2


print(max(solve(), solve()))
0