結果

問題 No.1773 Love Triangle
ユーザー 👑 hitonanodehitonanode
提出日時 2021-10-13 23:43:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 749 ms / 2,000 ms
コード長 1,462 bytes
コンパイル時間 340 ms
コンパイル使用メモリ 87,176 KB
実行使用メモリ 82,996 KB
最終ジャッジ日時 2023-09-16 22:09:04
合計ジャッジ時間 43,397 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 91 ms
72,196 KB
testcase_01 AC 97 ms
77,004 KB
testcase_02 AC 100 ms
77,616 KB
testcase_03 AC 124 ms
78,352 KB
testcase_04 AC 101 ms
77,524 KB
testcase_05 AC 113 ms
77,568 KB
testcase_06 AC 98 ms
76,572 KB
testcase_07 AC 107 ms
77,436 KB
testcase_08 AC 92 ms
72,188 KB
testcase_09 AC 105 ms
77,772 KB
testcase_10 AC 101 ms
77,580 KB
testcase_11 AC 129 ms
78,144 KB
testcase_12 AC 101 ms
77,740 KB
testcase_13 AC 91 ms
72,444 KB
testcase_14 AC 100 ms
77,716 KB
testcase_15 AC 114 ms
77,712 KB
testcase_16 AC 91 ms
72,100 KB
testcase_17 AC 124 ms
78,160 KB
testcase_18 AC 513 ms
81,748 KB
testcase_19 AC 109 ms
77,404 KB
testcase_20 AC 152 ms
78,592 KB
testcase_21 AC 93 ms
72,120 KB
testcase_22 AC 156 ms
78,640 KB
testcase_23 AC 125 ms
77,888 KB
testcase_24 AC 268 ms
80,236 KB
testcase_25 AC 249 ms
79,292 KB
testcase_26 AC 107 ms
78,080 KB
testcase_27 AC 104 ms
78,004 KB
testcase_28 AC 120 ms
77,912 KB
testcase_29 AC 94 ms
77,088 KB
testcase_30 AC 415 ms
79,188 KB
testcase_31 AC 316 ms
80,432 KB
testcase_32 AC 258 ms
79,136 KB
testcase_33 AC 143 ms
78,808 KB
testcase_34 AC 121 ms
78,352 KB
testcase_35 AC 106 ms
77,624 KB
testcase_36 AC 189 ms
79,060 KB
testcase_37 AC 89 ms
72,360 KB
testcase_38 AC 707 ms
82,556 KB
testcase_39 AC 706 ms
82,188 KB
testcase_40 AC 708 ms
82,528 KB
testcase_41 AC 731 ms
82,640 KB
testcase_42 AC 729 ms
82,564 KB
testcase_43 AC 718 ms
82,092 KB
testcase_44 AC 720 ms
82,364 KB
testcase_45 AC 702 ms
82,456 KB
testcase_46 AC 734 ms
82,584 KB
testcase_47 AC 717 ms
82,340 KB
testcase_48 AC 731 ms
82,720 KB
testcase_49 AC 739 ms
82,640 KB
testcase_50 AC 720 ms
82,552 KB
testcase_51 AC 721 ms
82,444 KB
testcase_52 AC 712 ms
82,300 KB
testcase_53 AC 719 ms
82,172 KB
testcase_54 AC 709 ms
82,320 KB
testcase_55 AC 723 ms
82,636 KB
testcase_56 AC 704 ms
82,140 KB
testcase_57 AC 718 ms
82,980 KB
testcase_58 AC 735 ms
82,720 KB
testcase_59 AC 736 ms
82,944 KB
testcase_60 AC 739 ms
82,216 KB
testcase_61 AC 736 ms
82,712 KB
testcase_62 AC 737 ms
82,704 KB
testcase_63 AC 737 ms
82,316 KB
testcase_64 AC 740 ms
82,436 KB
testcase_65 AC 737 ms
82,684 KB
testcase_66 AC 735 ms
82,952 KB
testcase_67 AC 740 ms
82,176 KB
testcase_68 AC 749 ms
82,604 KB
testcase_69 AC 734 ms
82,180 KB
testcase_70 AC 741 ms
82,492 KB
testcase_71 AC 740 ms
82,712 KB
testcase_72 AC 735 ms
82,440 KB
testcase_73 AC 741 ms
82,996 KB
testcase_74 AC 735 ms
82,468 KB
testcase_75 AC 740 ms
82,484 KB
testcase_76 AC 740 ms
82,520 KB
testcase_77 AC 732 ms
82,448 KB
testcase_78 AC 89 ms
72,116 KB
testcase_79 AC 105 ms
79,476 KB
testcase_80 AC 121 ms
77,988 KB
testcase_81 AC 736 ms
82,680 KB
testcase_82 AC 735 ms
82,168 KB
testcase_83 AC 258 ms
78,820 KB
testcase_84 AC 342 ms
78,944 KB
testcase_85 AC 512 ms
81,520 KB
testcase_86 AC 213 ms
78,376 KB
testcase_87 AC 361 ms
80,392 KB
testcase_88 AC 233 ms
79,780 KB
testcase_89 AC 288 ms
80,356 KB
testcase_90 AC 617 ms
82,496 KB
testcase_91 AC 452 ms
81,276 KB
testcase_92 AC 178 ms
78,584 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