結果
問題 | No.1773 Love Triangle |
ユーザー |
👑 |
提出日時 | 2021-10-12 22:48:51 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 126 ms / 2,000 ms |
コード長 | 4,045 bytes |
コンパイル時間 | 1,068 ms |
コンパイル使用メモリ | 35,160 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-03 21:04:24 |
合計ジャッジ時間 | 7,799 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 90 |
ソースコード
#include <stdio.h>#define DIM 500#define M_MAX 1000const int Mod = 30011;int div_mod(int x, int y, int z){if (x % y == 0) return x / y;else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;}int rank_matrix(int d, int A[][DIM]){if (d <= 0) return 1;int i, j, k, r, p[DIM], X[DIM][DIM], inv, tmp[DIM];for (i = 0; i < d; i++) p[i] = i;for (i = 0; i < d; i++) {for (j = 0; j < d; j++) {X[i][j] = A[i][j] % Mod;if (X[i][j] < 0) X[i][j] += Mod;}}for (i = 0, r = 0; i < d; i++) {for (j = r; j < d; j++) if (X[i][p[j]] != 0) break;if (j == d) continue;else if (j != r) {p[r] ^= p[j];p[j] ^= p[r];p[r] ^= p[j];}inv = div_mod(1, X[i][p[r]], Mod);for (k = i; k < d; k++) tmp[k] = X[k][p[r]] * inv % Mod;for (j = r + 1; j < d; j++) {if (X[i][p[j]] != 0) {for (k = i + 1; k < d; k++) {X[k][p[j]] -= tmp[k] * X[i][p[j]] % Mod;if (X[k][p[j]] < 0) X[k][p[j]] += Mod;}X[i][p[j]] = 0;}}r++;}return r;}#define MT_N 624#define MT_M 397#define MT_MATRIX_A 0x9908b0dfUL#define MT_UPPER_MASK 0x80000000UL#define MT_LOWER_MASK 0x7fffffffULstatic unsigned int mt[MT_N];static int mti = MT_N + 1;void init_genrand(unsigned int s){mt[0] = s & 0xffffffffUL;for (mti = 1; mti < MT_N; mti++) {mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);mt[mti] &= 0xffffffffUL;}}unsigned int genrand(){unsigned int y;static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A};if (mti >= MT_N) {int kk;if (mti == MT_N + 1) init_genrand(5489UL);for (kk = 0; kk < MT_N - MT_M; kk++) {y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL];}for (; kk < MT_N - 1; kk++) {y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL];}y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK);mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL];mti = 0;}y = mt[mti++];y ^= (y >> 11);y ^= (y << 7) & 0x9d2c5680UL;y ^= (y << 15) & 0xefc60000UL;y ^= (y >> 18);return y;}void chmax(int* a, int b){if (*a < b) *a = b;}int solve(int N, int M, int u[], int v[], int w[]){int i, j, ans = 0, Y[DIM][DIM] = {}, r;for (i = 1; i <= M; i++) {r = genrand() % Mod;Y[u[i]][v[i]] += r;if (Y[u[i]][v[i]] >= Mod) Y[u[i]][v[i]] -= Mod;Y[u[i]][w[i]] -= r;if (Y[u[i]][w[i]] < 0) Y[u[i]][w[i]] += Mod;Y[v[i]][u[i]] -= r;if (Y[v[i]][u[i]] < 0) Y[v[i]][u[i]] += Mod;Y[v[i]][w[i]] += r;if (Y[v[i]][w[i]] >= Mod) Y[v[i]][w[i]] -= Mod;Y[w[i]][u[i]] += r;if (Y[w[i]][u[i]] >= Mod) Y[w[i]][u[i]] -= Mod;Y[w[i]][v[i]] -= r;if (Y[w[i]][v[i]] < 0) Y[w[i]][v[i]] += Mod;}chmax(&ans, rank_matrix(N, Y));for (i = 1; i <= M; i++) {r = genrand() % Mod;Y[u[i]][v[i]] += r;if (Y[u[i]][v[i]] >= Mod) Y[u[i]][v[i]] -= Mod;Y[u[i]][w[i]] -= r;if (Y[u[i]][w[i]] < 0) Y[u[i]][w[i]] += Mod;Y[v[i]][u[i]] -= r;if (Y[v[i]][u[i]] < 0) Y[v[i]][u[i]] += Mod;Y[v[i]][w[i]] += r;if (Y[v[i]][w[i]] >= Mod) Y[v[i]][w[i]] -= Mod;Y[w[i]][u[i]] += r;if (Y[w[i]][u[i]] >= Mod) Y[w[i]][u[i]] -= Mod;Y[w[i]][v[i]] -= r;if (Y[w[i]][v[i]] < 0) Y[w[i]][v[i]] += Mod;}chmax(&ans, rank_matrix(N, Y));return ans / 2;}int main(){int i, j, N, M, u[M_MAX + 1], v[M_MAX + 1], w[M_MAX + 1];scanf("%d %d", &N, &M);if (3 > N || N > 500 || 1 > M || M > 1000 || M > N * (N - 1) * (N - 2) / 6) return -1;for (i = 1; i <= M; i++) {scanf("%d %d %d", &(u[i]), &(v[i]), &(w[i]));if (1 > u[i] || u[i] >= v[i] || v[i] >= w[i] || w[i] > N) return -1;u[i]--;v[i]--;w[i]--;for (j = 1; j < i; j++) if (u[j] == u[i] && v[j] == v[i] && w[j] == w[i]) return -1;}printf("%d\n", solve(N, M, u, v, w));fflush(stdout);return 0;}