#793738 (C++17) No.1773 Love Triangle

提出ソース

結果

問題	No.1773 Love Triangle
ユーザー	kazu0x17
提出日時	2022-08-28 20:46:19
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	791 ms / 2,000 ms
コード長	4,836 bytes
コンパイル時間	1,305 ms
コンパイル使用メモリ	116,932 KB
実行使用メモリ	15,104 KB
最終ジャッジ日時	2024-10-15 17:45:10
合計ジャッジ時間	36,225 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	3 ms 6,820 KB
testcase_03	AC	3 ms 6,816 KB
testcase_04	AC	3 ms 6,820 KB
testcase_05	AC	3 ms 6,816 KB
testcase_06	AC	3 ms 6,816 KB
testcase_07	AC	4 ms 6,820 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	3 ms 6,816 KB
testcase_11	AC	3 ms 6,820 KB
testcase_12	AC	3 ms 6,820 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	AC	3 ms 6,816 KB
testcase_15	AC	5 ms 6,820 KB
testcase_16	AC	1 ms 6,820 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	426 ms 12,544 KB
testcase_19	AC	9 ms 6,820 KB
testcase_20	AC	45 ms 6,816 KB
testcase_21	AC	1 ms 6,820 KB
testcase_22	AC	41 ms 6,816 KB
testcase_23	AC	30 ms 6,820 KB
testcase_24	AC	160 ms 9,984 KB
testcase_25	AC	157 ms 8,320 KB
testcase_26	AC	8 ms 6,816 KB
testcase_27	AC	9 ms 6,816 KB
testcase_28	AC	8 ms 6,816 KB
testcase_29	AC	1 ms 6,816 KB
testcase_30	AC	332 ms 10,880 KB
testcase_31	AC	212 ms 11,136 KB
testcase_32	AC	151 ms 12,928 KB
testcase_33	AC	47 ms 9,344 KB
testcase_34	AC	6 ms 6,820 KB
testcase_35	AC	12 ms 6,820 KB
testcase_36	AC	104 ms 6,816 KB
testcase_37	AC	2 ms 6,820 KB
testcase_38	AC	676 ms 14,464 KB
testcase_39	AC	658 ms 14,592 KB
testcase_40	AC	683 ms 14,464 KB
testcase_41	AC	750 ms 14,720 KB
testcase_42	AC	737 ms 14,976 KB
testcase_43	AC	730 ms 14,848 KB
testcase_44	AC	715 ms 14,720 KB
testcase_45	AC	666 ms 14,464 KB
testcase_46	AC	703 ms 14,976 KB
testcase_47	AC	720 ms 14,592 KB
testcase_48	AC	699 ms 14,848 KB
testcase_49	AC	684 ms 14,976 KB
testcase_50	AC	682 ms 14,592 KB
testcase_51	AC	751 ms 14,720 KB
testcase_52	AC	682 ms 14,464 KB
testcase_53	AC	669 ms 14,720 KB
testcase_54	AC	651 ms 14,592 KB
testcase_55	AC	705 ms 14,848 KB
testcase_56	AC	712 ms 14,464 KB
testcase_57	AC	696 ms 14,592 KB
testcase_58	AC	681 ms 14,976 KB
testcase_59	AC	687 ms 14,976 KB
testcase_60	AC	687 ms 14,976 KB
testcase_61	AC	688 ms 14,976 KB
testcase_62	AC	691 ms 15,104 KB
testcase_63	AC	666 ms 14,976 KB
testcase_64	AC	706 ms 14,976 KB
testcase_65	AC	697 ms 14,976 KB
testcase_66	AC	728 ms 15,104 KB
testcase_67	AC	690 ms 14,976 KB
testcase_68	AC	791 ms 14,976 KB
testcase_69	AC	686 ms 14,848 KB
testcase_70	AC	671 ms 14,848 KB
testcase_71	AC	695 ms 14,976 KB
testcase_72	AC	671 ms 14,848 KB
testcase_73	AC	714 ms 14,976 KB
testcase_74	AC	713 ms 14,976 KB
testcase_75	AC	696 ms 14,976 KB
testcase_76	AC	665 ms 14,976 KB
testcase_77	AC	690 ms 15,104 KB
testcase_78	AC	1 ms 6,820 KB
testcase_79	AC	15 ms 14,976 KB
testcase_80	AC	14 ms 14,976 KB
testcase_81	AC	529 ms 14,976 KB
testcase_82	AC	482 ms 14,976 KB
testcase_83	AC	160 ms 7,936 KB
testcase_84	AC	222 ms 9,984 KB
testcase_85	AC	349 ms 13,696 KB
testcase_86	AC	107 ms 7,680 KB
testcase_87	AC	216 ms 10,752 KB
testcase_88	AC	119 ms 14,464 KB
testcase_89	AC	160 ms 9,088 KB
testcase_90	AC	435 ms 14,720 KB
testcase_91	AC	318 ms 11,776 KB
testcase_92	AC	81 ms 7,040 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
        while(num > 0){
            if((num & 1) == 0){
                x *= x;
                if(x >= mod) x %= mod;
                num /= 2;
            }else{
                res = (res*x);
                if(res >= mod) res %= mod;
                num--;
            }
        }
        return res;
    }
    lli val;
    modint operator+(modint a){
        lli tmp = (val + a.val);
        if(tmp >= mod) tmp -= mod;
        return tmp;
    }
    modint operator-(modint a){
        lli tmp = (val + (mod - a.val));
        if(tmp >= mod) tmp -= mod;
        return tmp;
    }
    modint operator*(modint a){
        lli tmp = (val*a.val);
        if(tmp >= mod) tmp %= mod;
        return tmp;
    }
    modint operator/(modint a){
        lli tmp = (val*inv_mod(a.val));
        if(tmp >= mod) tmp %= mod;        
        return tmp;
    }
    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++)  {
    //     cout << "i: " << setw(2) << i << " ";
    //     for(int j = 0; j < M.size(); j++) {
    //         if(M[i][j].val != 0) cout << "1 ";
    //         else cout << "0 ";
    //     }
    //     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;
        // cout << "counter i:" << i << endl;
        z = M[i][pivot - 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].val != 0) cout << "1 ";
        //         else cout << "0 ";
        //     }
        //     cout << endl;
        // }

        // cout << "piv:" << pivot << ", i:" << i << ", n:" << M.size() << endl;
        // cout << "z:" << z.val << endl;
        for(int j = 0; j < M.size(); j++) M[i][j] = M[i][j] / z;
        // cout << "pivot:" << M[i][pivot-1].val << endl;
        for(int j = i+1; j < M.size(); j++) {
            modint w = M[j][pivot - 1];
            // cout << "w:" << w.val << endl;
            // cout << "i:" << i << ", j:" << j << ", pivot:" << pivot - 1 << endl;
            for(int k = 0; k < M.size(); k++){
                // cout << "i:" << i << ", k:" << k << ", M.val:" << M[i][k].val << ", w:" << w.val << ", w*M:" << (w*M[i][k]).val << endl;
                // cout << "pivo:" << (M[i][pivot-1]).val << endl;
                M[j][k] = M[j][k] - (w * M[i][k]); 
                // cout << "i:" << i << ", k:" << k << ", M.val:" << M[i][k].val << ", w:" << w.val << ", w*M:" << (w*M[i][k]).val << endl;
                // cout << endl;
            }  
        }
        // 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].val != 0) cout << "1 ";
    //         else cout << "0 ";
    //     }
    //     cout << endl;
    // }
    // for(int i = 0; i < M.size(); i++) {
    //     cout << M[i][i].val << " ";
    // }
    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 i = 0; i < t; i++) {
        ans = max(ans, Rank(M[i]));
    }
    cout << ans/2 << endl;
}

yukicoder

結果

テストケース

ソースコード