結果

問題 No.408 五輪ピック
ユーザー bal4u
提出日時 2019-08-01 21:58:36
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,118 bytes
コンパイル時間 1,125 ms
コンパイル使用メモリ 32,464 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-07-05 07:56:38
合計ジャッジ時間 8,613 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 15 TLE * 1 -- * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.1 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 > 1 && c != b && (dis[c] & 1)) {
			for (j = 0; j < hi[b]; j++) {
				d = to[b][j];
				if (d > 1 && d != a && d != c && (dis[d] & 1)) {
					printf("check: %d,%d <- %d,%d\n",a,b,c,d);
					return 1;
				}
			}
		}
	}
	return 0;
}

int main()
{
	int i, j, a, b, 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();
		insert(a, b), insert(b, a);
		memo[sz++] = a, memo[sz++] = b;
		hi[a]++, 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, to[b][hi[b]++] = a;
	}

	q[0].n = 1, q[0].t = 0, top = 0, end = 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