#462094 (C++14) No.1023 Cyclic Tour

提出ソース

結果

問題	No.1023 Cyclic Tour
ユーザー	QCFium
提出日時	2020-04-10 22:04:32
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	83 ms / 2,000 ms
コード長	1,435 bytes
コンパイル時間	1,872 ms
コンパイル使用メモリ	177,160 KB
実行使用メモリ	15,060 KB
最終ジャッジ日時	2024-09-15 20:25:00
合計ジャッジ時間	7,399 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	31 ms 5,376 KB
testcase_05	AC	31 ms 5,376 KB
testcase_06	AC	35 ms 5,376 KB
testcase_07	AC	32 ms 5,376 KB
testcase_08	AC	44 ms 8,380 KB
testcase_09	AC	44 ms 8,240 KB
testcase_10	AC	41 ms 8,116 KB
testcase_11	AC	46 ms 8,260 KB
testcase_12	AC	47 ms 9,164 KB
testcase_13	AC	44 ms 8,884 KB
testcase_14	AC	44 ms 8,752 KB
testcase_15	AC	46 ms 8,760 KB
testcase_16	AC	77 ms 10,584 KB
testcase_17	AC	78 ms 10,452 KB
testcase_18	AC	80 ms 10,288 KB
testcase_19	AC	79 ms 9,912 KB
testcase_20	AC	66 ms 7,624 KB
testcase_21	AC	69 ms 7,888 KB
testcase_22	AC	74 ms 8,396 KB
testcase_23	AC	77 ms 8,524 KB
testcase_24	AC	83 ms 9,656 KB
testcase_25	AC	67 ms 7,496 KB
testcase_26	AC	68 ms 7,612 KB
testcase_27	AC	64 ms 7,216 KB
testcase_28	AC	80 ms 9,664 KB
testcase_29	AC	79 ms 9,924 KB
testcase_30	AC	83 ms 9,552 KB
testcase_31	AC	75 ms 9,300 KB
testcase_32	AC	83 ms 10,808 KB
testcase_33	AC	82 ms 9,812 KB
testcase_34	AC	26 ms 5,376 KB
testcase_35	AC	57 ms 5,376 KB
testcase_36	AC	71 ms 7,908 KB
testcase_37	AC	74 ms 9,528 KB
testcase_38	AC	75 ms 9,908 KB
testcase_39	AC	75 ms 8,512 KB
testcase_40	AC	75 ms 8,644 KB
testcase_41	AC	75 ms 8,896 KB
testcase_42	AC	67 ms 7,752 KB
testcase_43	AC	77 ms 9,664 KB
testcase_44	AC	34 ms 6,400 KB
testcase_45	AC	54 ms 14,928 KB
testcase_46	AC	53 ms 15,060 KB
testcase_47	AC	34 ms 6,272 KB
testcase_48	AC	67 ms 7,640 KB
testcase_49	AC	68 ms 7,636 KB
testcase_50	AC	66 ms 7,508 KB
testcase_51	AC	67 ms 7,632 KB
testcase_52	AC	68 ms 7,504 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct UnionFind {
	std::vector<int> data;
	UnionFind (int size) : data(size, -1) {}
	bool unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x != y) {
			if (data[y] < data[x]) std::swap(x, y);
			data[x] += data[y];
			data[y] = x;
		}
		return x != y;
	}
	bool same(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
	bool connected() { return size(0) == (int) data.size(); }
};


std::vector<int> visited;
std::vector<std::vector<int> > hen;
bool dfs(int i) {
	visited[i] = 1;
	for (auto j : hen[i]) {
		if (visited[j] == 1) return true;
		if (visited[j] == 0 && dfs(j)) return true;
	}
	visited[i] = 2;
	return false;
}

bool solve() {
	int n = ri();
	int m = ri();
	UnionFind uni(n);
	std::vector<std::pair<int, int> > directed;
	for (int i = 0; i < m; i++) {
		int a = ri() - 1;
		int b = ri() - 1;
		int c = ri();
		if (c == 1 && !uni.unite(a, b)) return true;
		if (c == 2) directed.push_back({a, b});
	}
	for (auto &i : directed) i.first = uni.root(i.first), i.second = uni.root(i.second);
	hen.resize(n);
	for (auto i : directed) hen[i.first].push_back(i.second);
	visited.assign(n, 0);
	for (int i = 0; i < n; i++) if (!visited[i] && dfs(i)) return true;
	return false;
}

int main() {
	puts(solve() ? "Yes" : "No");
	return 0;
}

yukicoder

結果

テストケース

ソースコード