結果

問題 No.1773 Love Triangle
ユーザー kazu0x17kazu0x17
提出日時 2022-08-18 14:47:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 4,701 bytes
コンパイル時間 1,512 ms
コンパイル使用メモリ 114,828 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-10-06 05:38:32
合計ジャッジ時間 7,432 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

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

class rational{
public:
    rational(){x = 0, y = 1;}
    rational(lli a, lli b){x = a, y = b;}
    lli x, y;
    rational operator+(rational a){
        rational r((x*a.y + a.x*y), y*a.y);
        lli g = gcd(r.x, r.y);
        r.x /= g, r.y /= g;
        if(r.y < 0) r.x = -r.x, r.y = -r.y;
        return r;
    }
    rational operator-(rational a){
        rational r((x*a.y - a.x*y), y*a.y);
        lli g = gcd(r.x, r.y);
        r.x /= g, r.y /= g;
        if(r.y < 0) r.x = -r.x, r.y = -r.y;
        return r;
    }
    rational operator*(rational a){
        rational r(x*a.x, y*a.y);
        lli g = gcd(r.x, r.y);
        r.x /= g, r.y /= g;
        if(r.y < 0) r.x = -r.x, r.y = -r.y;
        return r;
    }
    rational operator/(rational a){
        if(a.x == 0){
            cerr << "divided by zero." << endl;
            exit(1);
        }
        rational r(x*a.y, y*a.x);
        lli g = gcd(r.x, r.y);
        r.x /= g, r.y /= g;
        if(r.y < 0) r.x = -r.x, r.y = -r.y;
        return r;
    }
};

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

int Rank(vector<vector<rational> > 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 = -1, r = 0;
    rational z;
    for(int i = 0; i < M.size(); i++) {
        // cout << "i:" << i  << ", pivot:" << pivot << ", n:" << M.size() << endl;
        for(int j = pivot + 1; j < M.size(); j++) {
            // cout << "j:" << j << endl;            
            pivot = 1e9;
            if(M[i][j].x != 0)pivot = j;
            for(int k = i+1; k < M.size() and M[i][j].x == 0; k++) {
                // cout << "hoge:" << M[i][j].x << endl;
                // cout << "fuga:" << M[k][j].x << endl;
                if(M[i][j].x == 0 and M[k][j].x != 0){
                    swap(M[i], M[k]);
                    // z = rational(M[i][j]);
                    pivot = j;
                    break;
                }
            }
            if(pivot == j) break;
        }
        if(pivot >= M.size() - 1) break; 
        z = M[i][pivot];

        // 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++) {
            rational w = M[j][pivot];
            // 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].x != 0) r = i;
        }
    }
    // for(int i = 0; i < M.size(); 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;
    // lli mod = 49725516559;
    lli mod = 1e9+7;
    cin >> n >> m;
    vector<vector<lli> > M(n, vector<lli>(n, 0));
    for(int i = 0; i < m; i++) {
        int x = rndgen(mt);
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--, w--;
        M[u][v] = (M[u][v] + x)%mod;
        M[v][w] = (M[v][w] + x)%mod;
        M[w][u] = (M[w][u] + x)%mod;

        M[v][u] = (M[v][u] - x + mod)%mod;
        M[w][v] = (M[w][v] - x + mod)%mod;
        M[u][w] = (M[u][w] - x + mod)%mod;
    }

    vector<vector<rational> > ratM(n, vector<rational>(n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            ratM[i][j] = rational(M[i][j], 1);
        }
    }
    int ans = 0;
    for(int i = 0; i < 10; i++) ans = max(ans, Rank(ratM));
    // for(int i = 0; i < n; i++) {
    //     for(int j = 0; j < n; j++) {
    //         ratM[i][j] = rational(1, 1);
    //     }
    // }
    // Rank(ratM);
    cout << ans/2 << endl;
}
0