結果

問題 No.826 連絡網
コンテスト
ユーザー MarcusAureliusAntoninus
提出日時 2019-05-03 22:07:15
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 58 ms / 2,000 ms
コード長 1,233 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,850 ms
コンパイル使用メモリ 214,396 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2026-06-07 11:40:23
合計ジャッジ時間 5,570 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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