結果

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

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#define DIM 500
#define M_MAX 1000
const 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 0x7fffffffUL
static 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0