結果
問題 | No.1773 Love Triangle |
ユーザー |
![]() |
提出日時 | 2022-08-28 20:46:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 851 ms / 2,000 ms |
コード長 | 4,836 bytes |
コンパイル時間 | 1,166 ms |
コンパイル使用メモリ | 113,644 KB |
最終ジャッジ日時 | 2025-02-06 23:03:24 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 90 |
ソースコード
#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;}