結果

問題 No.408 五輪ピック
ユーザー pekempey
提出日時 2016-08-05 22:43:01
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 351 ms
コード長 823 Byte
コンパイル時間 1,008 ms
使用メモリ 52,844 KB
最終ジャッジ日時 2019-08-25 21:01:48

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
00_example_01.in AC 42 ms
51,864 KB
00_example_02.in AC 41 ms
51,864 KB
00_example_03.in AC 41 ms
51,864 KB
00_example_04.in AC 42 ms
51,868 KB
00_example_05.in AC 41 ms
51,864 KB
10_rand_01.in AC 49 ms
52,376 KB
10_rand_02.in AC 175 ms
52,500 KB
10_rand_03.in AC 54 ms
52,604 KB
10_rand_04.in AC 48 ms
52,284 KB
10_rand_05.in AC 49 ms
52,388 KB
10_rand_06.in AC 175 ms
52,376 KB
10_rand_07.in AC 172 ms
52,348 KB
10_rand_08.in AC 234 ms
52,656 KB
10_rand_09.in AC 49 ms
52,504 KB
10_rand_10.in AC 87 ms
52,068 KB
20_max_01.in AC 49 ms
52,400 KB
20_max_02.in AC 50 ms
52,240 KB
20_max_03.in AC 52 ms
52,500 KB
20_max_04.in AC 54 ms
52,652 KB
20_max_05.in AC 54 ms
52,740 KB
30_grid_01.in AC 111 ms
52,228 KB
30_grid_02.in AC 79 ms
52,072 KB
30_grid_03.in AC 160 ms
52,476 KB
40_special_01.in AC 58 ms
52,712 KB
40_special_02.in AC 156 ms
52,540 KB
40_special_03.in AC 134 ms
52,544 KB
40_special_04.in AC 329 ms
52,844 KB
40_special_05.in AC 351 ms
52,504 KB
40_special_06.in AC 49 ms
52,240 KB
40_special_07.in AC 48 ms
52,336 KB
50_hand_01.in AC 41 ms
51,868 KB
50_hand_02.in AC 41 ms
51,864 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> g[20202];
bitset<20202> path[20202]; // last

bool solve() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		u--;
		v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	for (int i : g[0]) {
		for (int j : g[i]) if (j != 0) {
			path[j][i] = true;
		}
	}

	for (int i = 1; i < n; i++) {
		for (int j : g[i]) if (j != 0) {
			bool p1 = path[i][j];
			bool p2 = path[j][i];
			path[i][j] = false;
			path[j][i] = false;
			if (path[i].count() == 1 && path[j].count() == 1) {
				if ((path[i] & path[j]).none()) return true;
			} else if (path[i].count() >= 1 && path[j].count() >= 1) {
				return true;
			}
			path[i][j] = p1;
			path[j][i] = p2;
		}
	}

	return false;
}

int main() {
	puts(solve() ? "YES" : "NO");
}
0