結果

問題 No.1773 Love Triangle
ユーザー kazu0x17kazu0x17
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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;
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0