#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
• 実行時間: 481 ms / 2,000 ms
• コード長: 582 bytes
• コンパイル時間: 2,480 ms
• コンパイル使用メモリ: 197,852 KB
• 実行使用メモリ: 5,044 KB
• 最終ジャッジ日時: 2023-08-26 21:19:53
• 合計ジャッジ時間: 15,303 ms
• ジャッジサーバーID （参考情報）: judge11 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,380 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	434 ms; 4,836 KB
testcase_04	AC	238 ms; 4,380 KB
testcase_05	AC	161 ms; 4,376 KB
testcase_06	AC	55 ms; 4,376 KB
testcase_07	AC	371 ms; 4,380 KB
testcase_08	AC	252 ms; 4,876 KB
testcase_09	AC	321 ms; 4,376 KB
testcase_10	AC	351 ms; 4,376 KB
testcase_11	AC	291 ms; 4,736 KB
testcase_12	AC	369 ms; 4,588 KB
testcase_13	AC	448 ms; 4,908 KB
testcase_14	AC	452 ms; 5,044 KB
testcase_15	AC	461 ms; 4,864 KB
testcase_16	AC	449 ms; 5,004 KB
testcase_17	AC	457 ms; 5,000 KB
testcase_18	AC	481 ms; 4,980 KB
testcase_19	AC	447 ms; 5,044 KB
testcase_20	AC	434 ms; 4,856 KB
testcase_21	AC	440 ms; 4,860 KB
testcase_22	AC	431 ms; 4,860 KB
testcase_23	AC	385 ms; 4,864 KB
testcase_24	AC	407 ms; 4,860 KB
testcase_25	AC	397 ms; 4,880 KB
testcase_26	AC	386 ms; 4,904 KB
testcase_27	AC	288 ms; 4,376 KB
testcase_28	AC	2 ms; 4,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;
	}
}