結果

問題 No.408 五輪ピック
ユーザー bal4ubal4u
提出日時 2019-08-02 05:44:03
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 19 ms / 5,000 ms
コード長 2,401 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 33,092 KB
実行使用メモリ 7,168 KB
最終ジャッジ日時 2024-07-05 08:02:46
合計ジャッジ時間 1,518 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 9 ms
6,272 KB
testcase_06 AC 8 ms
6,528 KB
testcase_07 AC 9 ms
6,400 KB
testcase_08 AC 8 ms
6,144 KB
testcase_09 AC 7 ms
6,144 KB
testcase_10 AC 8 ms
6,144 KB
testcase_11 AC 8 ms
6,016 KB
testcase_12 AC 10 ms
6,400 KB
testcase_13 AC 9 ms
6,144 KB
testcase_14 AC 6 ms
5,888 KB
testcase_15 AC 6 ms
5,376 KB
testcase_16 AC 9 ms
6,400 KB
testcase_17 AC 10 ms
6,272 KB
testcase_18 AC 10 ms
6,400 KB
testcase_19 AC 11 ms
6,656 KB
testcase_20 AC 6 ms
6,016 KB
testcase_21 AC 6 ms
5,760 KB
testcase_22 AC 8 ms
6,528 KB
testcase_23 AC 19 ms
7,168 KB
testcase_24 AC 12 ms
6,784 KB
testcase_25 AC 5 ms
5,376 KB
testcase_26 AC 10 ms
6,912 KB
testcase_27 AC 5 ms
5,376 KB
testcase_28 AC 8 ms
6,272 KB
testcase_29 AC 9 ms
6,272 KB
testcase_30 AC 1 ms
5,376 KB
testcase_31 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:9:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
    9 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:14:24: note: in expansion of macro 'gc'
   14 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff # 

// yukicoder: No.408 五輪ピック
// 2019.8.2 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

// 数値のハッシュ関数
#define HASHSIZ 1000003
int hash[HASHSIZ+5], *hashend = hash+HASHSIZ;

int lookup(int a, int b) {
	int t, *p;
	t = (a << 15) | b;
	p = hash + t % HASHSIZ;
	while (*p) {
		if (*p == t) return 1;
		if (++p == hashend) p = hash;
	}
	return 0;
}

void insert(int a, int b) {
	int t, *p;
	t = (a << 15) | b;
	p = hash + t % HASHSIZ;
	while (*p) {
		if (*p == t) return;
		if (++p == hashend) p = hash;
	}
	*p = t;
}


typedef struct { int n, t; } Q;
Q q[2000004]; int top, end;

int N, M;
int hi[20004], *to[20004];
char dis[20004];

int check(int a, int b) {
	int i, j, c, d;
	for (i = 0; i < hi[a]; i++) {
		c = to[a][i];
		if (c != b && (dis[c] & 1)) {
			for (j = 0; j < hi[b]; j++) {
				d = to[b][j];
				if (d != a && d != c && (dis[d] & 1)) {
					return 1;
				}
			}
		}
	}
	return 0;
}

int main()
{
	int i, j, a, b, c, t;
	int *memo, sz;
	
	N = in(), M = in();
	memo = malloc(M*2*sizeof(int));
	sz = 0; for (i = 0; i < M; i++) {
		a = in(), b = in();
		if (a > b) t = a, a = b, b = t;
		insert(a, b);
		memo[sz++] = a, memo[sz++] = b;
		hi[a]++;
		if (a > 1) hi[b]++;
	}
	for (i = 1; i <= N; i++) if (hi[i]) to[i] = malloc(sizeof(int)*hi[i]);
	memset(hi, 0, sizeof(int)*(N+1));
	i = 0; while (i < sz) {
		a = memo[i++], b = memo[i++];
		to[a][hi[a]++] = b;
		if (a > 1) to[b][hi[b]++] = a;
	}
	for (i = 0; i < hi[1]; i++) {
		a = to[1][i];
		if (hi[a] == 1) {
			b = to[a][0];
			if (hi[b] == 1) {
				hi[a] = hi[b] = 0;
				continue;
			}
		} else if (hi[a] == 2) {
			b = to[a][0], c = to[a][1];
			if (hi[b] == 1 && hi[c] == 1) {
				hi[a] = hi[b] = hi[c] = 0;
				continue;
			}
		}
		q[end].n = a, q[end++].t = 1, dis[a] = 1;
	}
	
	while (top != end) {
		a = q[top].n, t = q[top++].t;
		if (t >= 2) continue;
		t++;
		for (i = 0; i < hi[a]; i++) {
			b = to[a][i];
			if ((dis[b] & t) != t) {
				dis[b] |= t, q[end].n = b, q[end++].t = t;
			}
		}
	}

	for (a = 2; a <= N; a++) if (dis[a] & 2) {
		for (b = a+1; b <= N; b++) if (dis[b] & 2) {
			if (lookup(a, b) && check(a, b)) { puts("YES"); return 0; }
		}
	}
	puts("NO");
	return 0;
}
0