結果

問題 No.1773 Love Triangle
ユーザー kazu0x17kazu0x17
提出日時 2022-08-28 19:18:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,132 bytes
コンパイル時間 1,103 ms
コンパイル使用メモリ 116,444 KB
実行使用メモリ 15,232 KB
最終ジャッジ日時 2024-04-23 16:17:59
合計ジャッジ時間 30,386 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 WA -
testcase_03 AC 3 ms
5,376 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 4 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 32 ms
5,376 KB
testcase_21 WA -
testcase_22 AC 32 ms
5,376 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 6 ms
5,376 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 5 ms
5,376 KB
testcase_35 WA -
testcase_36 AC 77 ms
5,504 KB
testcase_37 WA -
testcase_38 AC 525 ms
14,592 KB
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 AC 535 ms
14,592 KB
testcase_53 AC 527 ms
14,720 KB
testcase_54 WA -
testcase_55 WA -
testcase_56 AC 529 ms
14,720 KB
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 WA -
testcase_63 WA -
testcase_64 AC 572 ms
15,104 KB
testcase_65 WA -
testcase_66 WA -
testcase_67 WA -
testcase_68 WA -
testcase_69 WA -
testcase_70 WA -
testcase_71 WA -
testcase_72 WA -
testcase_73 WA -
testcase_74 WA -
testcase_75 WA -
testcase_76 WA -
testcase_77 WA -
testcase_78 AC 2 ms
5,376 KB
testcase_79 WA -
testcase_80 WA -
testcase_81 WA -
testcase_82 WA -
testcase_83 WA -
testcase_84 WA -
testcase_85 WA -
testcase_86 WA -
testcase_87 WA -
testcase_88 WA -
testcase_89 WA -
testcase_90 WA -
testcase_91 WA -
testcase_92 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<random>
#include<vector>
#include <sstream>
#include <iomanip>
#include<chrono>
#include<tuple>
#include<numeric>
using namespace std;
using lli = long long int;

class modint{
public:
    modint(){val = 0;}
    modint(lli x){val = x;}
    lli inv_mod(lli x){
        lli num = mod - 2, res = 1, p = x;
        while(num > 0){
            if((num & 1) == 0){
                p = (p*p);
                if(p >= mod) p %= mod;
                num /= 2;
            }else{
                res = (res*p);
                if(res >= mod) res %= mod;
                num--;
            }
        }
        return res;
    }
    lli val;
    modint operator+(modint a){
        val = (val + a.val);
        if(val >= mod) val -= mod;
        return val;
    }
    modint operator-(modint a){
        val = (val + (mod - a.val));
        if(val >= mod) val -= mod;
        return val;
    }
    modint operator*(modint a){
        val = (val*a.val);
        if(val >= mod) val %= mod;
        return val;
    }
    modint operator/(modint a){
        val = (val*inv_mod(a.val));
        if(val >= mod) val %= mod;        
        return val;
    }
    lli mod = 1e9+7;
};

mt19937 mt(234298343);
// uniform_int_distribution<lli> rndgen(0, 49725516559);
uniform_int_distribution<lli> rndgen(0, 1e9+7-1);

int Rank(vector<vector<modint> > M){
    // for(int i = 0; i < M.size(); i++)  {
    //     for(int j = 0; j < M.size(); j++) {
    //         cout << M[i][j].x << "/" << M[i][j].y << " ";
    //     }
    //     cout << endl;
    // }
    // cout << endl;
    // cout << endl;

    int pivot = 0, r = 0;
    modint z;
    for(int i = 0; i < M.size(); i++) {
        // cout << "i:" << i  << ", pivot:" << pivot << ", n:" << M.size() << endl;
        while(pivot < M.size()){
            for(int j = i + 1; j < M.size(); j++) {
                if(M[j][pivot].val != 0 and M[i][pivot].val == 0) swap(M[i], M[j]);
            }
            if(M[i][pivot++].val != 0) break;
        }
        if(pivot == M.size() and M[i][pivot - 1].val == 0) break;
        z = M[i][pivot - 1];

        // for(int i = 0; i < M.size(); i++)  {
        //     for(int j = 0; j < M.size(); j++) {
        //         cout << M[i][j].x << "/" << M[i][j].y << " ";
        //     }
        //     cout << endl;
        // }
        // cout << "piv:" << pivot << ", i:" << i << ", n:" << M.size() << endl;
        // cout << "z:" << z.x << "/" << z.y << endl;
        for(int j = 0; j < M.size(); j++) M[i][j] = M[i][j] / z;
        for(int j = i+1; j < M.size(); j++) {
            modint w = M[j][pivot - 1];
            // cout << "wwww:" << w.x << "/" << w.y << endl;
            for(int k = 0; k < M.size(); k++)  M[j][k] = M[j][k] - (w * M[i][k]);
        }
        // cout << endl;
        // cout << endl;
    }
    r = 1e9;
    for(int i = M.size() - 1; i >= 0 and r == 1e9; i--)  {
        for(int j = 0; j < M.size() and r == 1e9; j++) {
            if(M[i][j].val != 0) r = i + 1;
        }
    }
    // for(int i = 0; i < M.size(); i++)  {
    //     cout << "i: " << setw(2) << i << " ";
    //     for(int j = 0; j < M.size(); j++) {
    //         if(M[i][j].x != 0) cout << "1 ";
    //         else cout << "0 ";
    //     }
        // for(int j = 0; j < M.size(); j++) {
        //     cout << M[i][j].x << "/" << M[i][j].y << " ";
        // }
        // cout << endl;
    // }
    return r;
}

int main(){
    int n, m, t = 2;
    cin >> n >> m;
    vector<vector<vector<modint> > > M(t, vector<vector<modint> >(n, vector<modint>(n, 0)));
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--, w--;
        for(int j = 0; j < t; j++) {
            modint x(rndgen(mt));
            M[j][u][v] = (M[j][u][v] + x);
            M[j][v][w] = (M[j][v][w] + x);
            M[j][w][u] = (M[j][w][u] + x);

            M[j][v][u] = (M[j][v][u] - x);
            M[j][w][v] = (M[j][w][v] - x);
            M[j][u][w] = (M[j][u][w] - x);
        }
    }

    int ans = 0;
    for(int k = 0; k < t; k++) {
        ans = max(ans, Rank(M[k]));
    }
    cout << ans/2 << endl;
}
0