結果

問題 No.1773 Love Triangle
ユーザー hitonanodehitonanode
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
55,780 KB
testcase_01 AC 50 ms
62,792 KB
testcase_02 AC 54 ms
63,800 KB
testcase_03 AC 74 ms
73,572 KB
testcase_04 AC 50 ms
64,572 KB
testcase_05 AC 59 ms
67,128 KB
testcase_06 AC 47 ms
63,716 KB
testcase_07 AC 51 ms
66,312 KB
testcase_08 AC 40 ms
55,724 KB
testcase_09 AC 50 ms
64,644 KB
testcase_10 AC 49 ms
63,736 KB
testcase_11 AC 72 ms
75,084 KB
testcase_12 AC 47 ms
62,776 KB
testcase_13 AC 40 ms
55,172 KB
testcase_14 AC 48 ms
62,716 KB
testcase_15 AC 62 ms
68,316 KB
testcase_16 AC 41 ms
54,688 KB
testcase_17 AC 74 ms
72,656 KB
testcase_18 AC 488 ms
80,380 KB
testcase_19 AC 54 ms
65,924 KB
testcase_20 AC 98 ms
76,996 KB
testcase_21 AC 41 ms
54,740 KB
testcase_22 AC 103 ms
77,496 KB
testcase_23 AC 74 ms
72,496 KB
testcase_24 AC 210 ms
76,372 KB
testcase_25 AC 201 ms
77,564 KB
testcase_26 AC 52 ms
64,200 KB
testcase_27 AC 52 ms
64,584 KB
testcase_28 AC 67 ms
72,256 KB
testcase_29 AC 45 ms
62,680 KB
testcase_30 AC 378 ms
79,676 KB
testcase_31 AC 264 ms
78,148 KB
testcase_32 AC 208 ms
78,244 KB
testcase_33 AC 94 ms
69,984 KB
testcase_34 AC 70 ms
72,872 KB
testcase_35 AC 57 ms
66,132 KB
testcase_36 AC 138 ms
77,512 KB
testcase_37 AC 42 ms
55,336 KB
testcase_38 AC 616 ms
81,144 KB
testcase_39 AC 620 ms
81,184 KB
testcase_40 AC 618 ms
81,248 KB
testcase_41 AC 641 ms
81,592 KB
testcase_42 AC 634 ms
80,820 KB
testcase_43 AC 623 ms
81,100 KB
testcase_44 AC 626 ms
81,108 KB
testcase_45 AC 616 ms
81,044 KB
testcase_46 AC 636 ms
80,992 KB
testcase_47 AC 625 ms
80,900 KB
testcase_48 AC 624 ms
81,360 KB
testcase_49 AC 628 ms
81,800 KB
testcase_50 AC 620 ms
81,032 KB
testcase_51 AC 615 ms
81,152 KB
testcase_52 AC 603 ms
80,792 KB
testcase_53 AC 610 ms
80,736 KB
testcase_54 AC 597 ms
80,688 KB
testcase_55 AC 609 ms
81,328 KB
testcase_56 AC 602 ms
80,696 KB
testcase_57 AC 617 ms
80,896 KB
testcase_58 AC 641 ms
81,124 KB
testcase_59 AC 639 ms
81,092 KB
testcase_60 AC 632 ms
81,148 KB
testcase_61 AC 628 ms
81,280 KB
testcase_62 AC 647 ms
81,304 KB
testcase_63 AC 626 ms
80,856 KB
testcase_64 AC 626 ms
81,328 KB
testcase_65 AC 624 ms
81,248 KB
testcase_66 AC 621 ms
81,340 KB
testcase_67 AC 632 ms
81,264 KB
testcase_68 AC 620 ms
81,364 KB
testcase_69 AC 626 ms
81,172 KB
testcase_70 AC 636 ms
80,868 KB
testcase_71 AC 630 ms
81,252 KB
testcase_72 AC 621 ms
81,504 KB
testcase_73 AC 617 ms
81,344 KB
testcase_74 AC 621 ms
81,224 KB
testcase_75 AC 624 ms
81,372 KB
testcase_76 AC 618 ms
81,240 KB
testcase_77 AC 628 ms
81,396 KB
testcase_78 AC 41 ms
55,024 KB
testcase_79 AC 52 ms
66,652 KB
testcase_80 AC 69 ms
72,024 KB
testcase_81 AC 638 ms
81,096 KB
testcase_82 AC 630 ms
81,080 KB
testcase_83 AC 216 ms
78,000 KB
testcase_84 AC 311 ms
78,096 KB
testcase_85 AC 484 ms
80,148 KB
testcase_86 AC 160 ms
77,360 KB
testcase_87 AC 310 ms
78,184 KB
testcase_88 AC 186 ms
78,384 KB
testcase_89 AC 237 ms
77,840 KB
testcase_90 AC 599 ms
81,424 KB
testcase_91 AC 428 ms
80,440 KB
testcase_92 AC 127 ms
77,148 KB
権限があれば一括ダウンロードができます

ソースコード

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