結果

問題 No.1773 Love Triangle
ユーザー 👑 hitonanodehitonanode
提出日時 2021-10-07 23:55:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 688 ms / 2,000 ms
コード長 1,538 bytes
コンパイル時間 1,881 ms
コンパイル使用メモリ 86,896 KB
実行使用メモリ 82,936 KB
最終ジャッジ日時 2023-09-16 22:02:04
合計ジャッジ時間 40,718 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
71,876 KB
testcase_01 AC 98 ms
76,656 KB
testcase_02 AC 90 ms
77,208 KB
testcase_03 AC 112 ms
77,804 KB
testcase_04 AC 89 ms
77,452 KB
testcase_05 AC 96 ms
77,404 KB
testcase_06 AC 86 ms
76,760 KB
testcase_07 AC 94 ms
77,316 KB
testcase_08 AC 78 ms
72,044 KB
testcase_09 AC 93 ms
77,432 KB
testcase_10 AC 95 ms
77,148 KB
testcase_11 AC 123 ms
78,092 KB
testcase_12 AC 94 ms
77,592 KB
testcase_13 AC 82 ms
72,292 KB
testcase_14 AC 92 ms
77,212 KB
testcase_15 AC 101 ms
77,336 KB
testcase_16 AC 82 ms
71,888 KB
testcase_17 AC 109 ms
78,048 KB
testcase_18 AC 470 ms
81,436 KB
testcase_19 AC 94 ms
77,684 KB
testcase_20 AC 133 ms
78,524 KB
testcase_21 AC 79 ms
71,904 KB
testcase_22 AC 133 ms
78,592 KB
testcase_23 AC 109 ms
77,716 KB
testcase_24 AC 238 ms
80,220 KB
testcase_25 AC 219 ms
79,516 KB
testcase_26 AC 90 ms
77,824 KB
testcase_27 AC 88 ms
77,568 KB
testcase_28 AC 105 ms
78,100 KB
testcase_29 AC 81 ms
76,584 KB
testcase_30 AC 366 ms
78,780 KB
testcase_31 AC 280 ms
80,348 KB
testcase_32 AC 224 ms
79,248 KB
testcase_33 AC 128 ms
78,768 KB
testcase_34 AC 109 ms
78,036 KB
testcase_35 AC 96 ms
77,580 KB
testcase_36 AC 167 ms
78,856 KB
testcase_37 AC 80 ms
71,888 KB
testcase_38 AC 653 ms
82,352 KB
testcase_39 AC 652 ms
82,080 KB
testcase_40 AC 655 ms
82,352 KB
testcase_41 AC 678 ms
82,660 KB
testcase_42 AC 666 ms
82,548 KB
testcase_43 AC 654 ms
82,568 KB
testcase_44 AC 648 ms
82,336 KB
testcase_45 AC 622 ms
82,316 KB
testcase_46 AC 653 ms
82,240 KB
testcase_47 AC 649 ms
81,988 KB
testcase_48 AC 678 ms
82,244 KB
testcase_49 AC 683 ms
82,392 KB
testcase_50 AC 657 ms
82,264 KB
testcase_51 AC 657 ms
82,644 KB
testcase_52 AC 651 ms
82,156 KB
testcase_53 AC 655 ms
82,256 KB
testcase_54 AC 646 ms
82,300 KB
testcase_55 AC 645 ms
82,188 KB
testcase_56 AC 627 ms
82,228 KB
testcase_57 AC 645 ms
82,640 KB
testcase_58 AC 669 ms
82,272 KB
testcase_59 AC 679 ms
82,400 KB
testcase_60 AC 688 ms
82,368 KB
testcase_61 AC 674 ms
82,536 KB
testcase_62 AC 672 ms
82,260 KB
testcase_63 AC 686 ms
82,420 KB
testcase_64 AC 679 ms
82,848 KB
testcase_65 AC 663 ms
82,936 KB
testcase_66 AC 674 ms
82,736 KB
testcase_67 AC 670 ms
82,276 KB
testcase_68 AC 674 ms
82,468 KB
testcase_69 AC 675 ms
82,256 KB
testcase_70 AC 683 ms
82,268 KB
testcase_71 AC 683 ms
82,648 KB
testcase_72 AC 670 ms
82,256 KB
testcase_73 AC 680 ms
82,656 KB
testcase_74 AC 678 ms
82,408 KB
testcase_75 AC 676 ms
82,356 KB
testcase_76 AC 673 ms
82,420 KB
testcase_77 AC 650 ms
82,248 KB
testcase_78 AC 81 ms
72,228 KB
testcase_79 AC 89 ms
79,512 KB
testcase_80 AC 102 ms
77,588 KB
testcase_81 AC 668 ms
82,112 KB
testcase_82 AC 670 ms
82,460 KB
testcase_83 AC 241 ms
78,620 KB
testcase_84 AC 323 ms
79,016 KB
testcase_85 AC 479 ms
81,236 KB
testcase_86 AC 197 ms
78,576 KB
testcase_87 AC 334 ms
80,280 KB
testcase_88 AC 212 ms
79,592 KB
testcase_89 AC 261 ms
79,904 KB
testcase_90 AC 576 ms
82,380 KB
testcase_91 AC 418 ms
81,260 KB
testcase_92 AC 161 ms
78,388 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
import random

random.seed(530629)

md = (1 << 29) + 11  # prime


def modinv(a: int) -> int:
    a2 = a * a % md
    a4 = a2 * a2 % md
    a8 = a4 * a4 % md
    x = a8
    for _ in range(26):
        x = x * x % md
    return x * a8 % md * 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