#873098 (C++17) No.2316 Freight Train

• 問題: No.2316 Freight Train
• ユーザー: Carpenters-Cat
• 提出日時: 2023-05-27 14:47:22
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 480 ms / 2,000 ms
• コード長: 582 bytes
• コンパイル時間: 2,268 ms
• コンパイル使用メモリ: 200,700 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-07 16:49:19
• 合計ジャッジ時間: 14,500 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	476 ms; 5,376 KB
testcase_04	AC	241 ms; 5,376 KB
testcase_05	AC	176 ms; 5,376 KB
testcase_06	AC	57 ms; 5,376 KB
testcase_07	AC	392 ms; 5,376 KB
testcase_08	AC	268 ms; 5,376 KB
testcase_09	AC	341 ms; 5,376 KB
testcase_10	AC	367 ms; 5,376 KB
testcase_11	AC	319 ms; 5,376 KB
testcase_12	AC	392 ms; 5,376 KB
testcase_13	AC	466 ms; 5,376 KB
testcase_14	AC	470 ms; 5,376 KB
testcase_15	AC	470 ms; 5,376 KB
testcase_16	AC	469 ms; 5,376 KB
testcase_17	AC	479 ms; 5,376 KB
testcase_18	AC	467 ms; 5,376 KB
testcase_19	AC	460 ms; 5,376 KB
testcase_20	AC	480 ms; 5,376 KB
testcase_21	AC	477 ms; 5,376 KB
testcase_22	AC	469 ms; 5,376 KB
testcase_23	AC	418 ms; 5,376 KB
testcase_24	AC	451 ms; 5,376 KB
testcase_25	AC	431 ms; 5,376 KB
testcase_26	AC	422 ms; 5,376 KB
testcase_27	AC	327 ms; 5,376 KB
testcase_28	AC	2 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
int par[200020];
int siz[200020];
int root(int a) {
	return (a == par[a] ? a : root(par[a]));
}
void merge(int a, int b) {
	a = root(a);
	b = root(b);
	if (a == b) return;
	if (siz[a] < siz[b]) swap(a, b);
	par[b] = a;
	siz[a] += siz[b];
}
int main () {
	int N, Q;
	cin >> N >> Q;
	iota(par, par + N, 0);
	fill(siz, siz + N, 1);
	for (int i = 0; i < N; i ++) {
		int p;
		cin >> p;
		p --;
		if (p >= 0) {
			merge(p, i);
		}
	}
	while (Q--) {
		int a, b;
		cin >> a >> b;
		cout << (root(--a) == root(--b) ? "Yes" : "No") << endl;
	}
}