結果
問題 | No.1773 Love Triangle |
ユーザー |
|
提出日時 | 2023-05-04 22:13:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 256 ms / 2,000 ms |
コード長 | 1,136 bytes |
コンパイル時間 | 1,972 ms |
コンパイル使用メモリ | 169,168 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-22 12:01:12 |
合計ジャッジ時間 | 14,980 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 90 |
ソースコード
#include <bits/stdc++.h> const int mod=1e9+7; using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n,m,u[1010][3],a[510][510]; void qmo(int &x){ x+=(x>>31)&mod; } int ksm(int a,int k){ int res=1; for(;k;k>>=1,a=1ll*a*a%mod) if(k&1) res=1ll*res*a%mod; return res; } int qry_rank(){ int k=0; for(int j=1;j<=n;j++){ int p=0; for(int i=k+1;i<=n;i++) if(a[i][j]){ p=i; break; } if(!p) continue; k++; for(int i=1;i<=n;i++) swap(a[p][i],a[k][i]); int inv=ksm(a[k][j],mod-2); for(int i=1;i<=n;i++) a[k][i]=1ll*a[k][i]*inv%mod; for(int i=k+1;i<=n;i++) if(a[i][j]){ int mul=a[i][j]; for(int l=1;l<=n;l++) a[i][l]=(a[i][l]-1ll*mul*a[k][l]%mod+mod)%mod; } } return k; } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<m;i++) for(int j=0;j<3;j++) scanf("%d",&u[i][j]); int k=0; for(int _=0;_<2;_++){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=0; for(int i=0;i<m;i++){ int x=rng()%mod; for(int j=0;j<3;j++){ qmo(a[u[i][j]][u[i][(j+1)%3]]+=x-mod); qmo(a[u[i][(j+1)%3]][u[i][j]]-=x); } } k=max(k,qry_rank()); } printf("%d\n",k/2); }