結果

問題 No.826 連絡網
ユーザー MarcusAureliusAntoninusMarcusAureliusAntoninus
提出日時 2019-05-03 22:07:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 69 ms / 2,000 ms
コード長 1,233 bytes
コンパイル時間 2,280 ms
コンパイル使用メモリ 201,316 KB
実行使用メモリ 11,000 KB
最終ジャッジ日時 2023-08-15 18:20:00
合計ジャッジ時間 4,150 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 49 ms
8,916 KB
testcase_13 AC 18 ms
5,384 KB
testcase_14 AC 35 ms
7,252 KB
testcase_15 AC 5 ms
4,376 KB
testcase_16 AC 23 ms
5,940 KB
testcase_17 AC 19 ms
5,488 KB
testcase_18 AC 14 ms
4,892 KB
testcase_19 AC 58 ms
9,476 KB
testcase_20 AC 57 ms
9,800 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 18 ms
5,412 KB
testcase_23 AC 24 ms
6,052 KB
testcase_24 AC 10 ms
4,376 KB
testcase_25 AC 68 ms
10,836 KB
testcase_26 AC 13 ms
4,564 KB
testcase_27 AC 50 ms
9,036 KB
testcase_28 AC 38 ms
7,536 KB
testcase_29 AC 18 ms
5,480 KB
testcase_30 AC 69 ms
11,000 KB
testcase_31 AC 22 ms
5,688 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