結果

問題 No.826 連絡網
ユーザー MarcusAureliusAntoninusMarcusAureliusAntoninus
提出日時 2019-05-03 22:07:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 1,233 bytes
コンパイル時間 2,121 ms
コンパイル使用メモリ 203,916 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-05-03 05:10:31
合計ジャッジ時間 3,739 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 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 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 48 ms
9,088 KB
testcase_13 AC 18 ms
5,632 KB
testcase_14 AC 35 ms
7,680 KB
testcase_15 AC 5 ms
5,376 KB
testcase_16 AC 23 ms
6,272 KB
testcase_17 AC 19 ms
5,632 KB
testcase_18 AC 15 ms
5,376 KB
testcase_19 AC 61 ms
9,984 KB
testcase_20 AC 58 ms
9,856 KB
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 19 ms
5,632 KB
testcase_23 AC 24 ms
6,272 KB
testcase_24 AC 11 ms
5,376 KB
testcase_25 AC 73 ms
11,264 KB
testcase_26 AC 13 ms
5,376 KB
testcase_27 AC 52 ms
9,344 KB
testcase_28 AC 38 ms
7,936 KB
testcase_29 AC 19 ms
5,632 KB
testcase_30 AC 73 ms
11,264 KB
testcase_31 AC 22 ms
6,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

//////////////////
// Union-Find木 //
//////////////////

// 0-indexed
class UnionFind {
private:
	std::vector<int> parent_, size_;
public:
	UnionFind(const int size)
		:parent_(size), size_(size, 1)
	{
		for (int i{}; i < size; i++) parent_[i] = i;
	}
	int calcRoot(const int index)
	{
		if (parent_[index] == index) return index;
		const int p{calcRoot(parent_[index])};
		parent_[index] = p;
		return p;
	}
	bool areConnected(const int index1, const int index2)
	{
		return calcRoot(index1) == calcRoot(index2);
	}
	void unite(const int index1, const int index2)
	{
		const int root1{calcRoot(index1)}, root2{calcRoot(index2)};
		if (root1 == root2) return;
		if (size_[root1] <= size_[root2])
		{
			size_[root2] += size_[root1];
			parent_[root1] = root2;
		}
		else
		{
			size_[root1] += size_[root2];
			parent_[root2] = root1;
		}
		return;
	}
	int calcSize(const int index)
	{
		return size_[calcRoot(index)];
	}
};

int main()
{
	int N, P;
	scanf("%d%d", &N, &P);
	UnionFind uf(N + 1);
	std::vector<bool> is_prime(N + 1, true);
	for (int i{2}; i <= N; i++)
	{
		if (!is_prime[i]) continue;
		for (int j{2 * i}; j <= N; j += i)
			uf.unite(i, j);
	}
	printf("%d\n", uf.calcSize(P));

	return 0;
}
0