結果

問題 No.629 グラフの中に眠る門松列
コンテスト
ユーザー bal4u
提出日時 2019-07-27 20:45:23
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 4,000 ms
コード長 1,406 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 31,872 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-02 11:12:18
合計ジャッジ時間 1,535 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:15:24: note: in expansion of macro 'gc'
   15 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff # 

// yukicoder: No.629 グラフの中に眠る門松列
// 2019.7.27 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;
}

int N;
int a[1003];
int *to[1003], hi[1003];

int check(int x1, int x2, int x3) {
	if (x1 == x3) return 0;
	if (x2 > x1 && x2 > x3) return 1;
	if (x2 < x1 && x2 < x3) return 1;
	return 0;
}

int bfs(int par) {
	int i, j, u;
	for (i = 0; i < hi[par]; i++) {
		u = to[par][i];
		for (j = 0; j < hi[u]; j++) if (to[u][j] != par) {
			if (check(a[par], a[u], a[to[u][j]])) return 1;
		}
	}
	return 0;
}
				
int main()
{
	int i, M, u, v;
	int *memo, sz;
	
	N = in(); M = in();
	a[1] = u = in(); for (i = 2; i <= N; i++) {
		a[i] = in(); if (a[i] != u) { u = -1; break; }
	}
	while (++i <= N) a[i] = in();
	if (u > 0) { puts("NO"); return 0; }
	
	memo = malloc(M*sizeof(int)*2);
	sz = 0; while (M--) {
		memo[sz++] = u = in(), memo[sz++] = v = in();
		hi[u]++, hi[v]++;
	}
	for (i = 1; i <= N; i++) if (hi[i])	to[i] = malloc(hi[i]*sizeof(int));
	memset(hi, 0, sizeof(hi));
	i = 0; while (i < sz) {
		u = memo[i++], v = memo[i++];
		to[u][hi[u]++] = v, to[v][hi[v]++] = u;
	}
	for (i = 1; i <= N; i++) {
		if (bfs(i)) { puts("YES"); return 0; }
	}
	puts("NO");
	return 0;
}
0