結果

問題 No.826 連絡網
ユーザー MarcusAureliusAntoninus
提出日時 2019-05-03 22:07:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 81 ms / 2,000 ms
コード長 1,233 bytes
コンパイル時間 2,325 ms
コンパイル使用メモリ 196,260 KB
最終ジャッジ日時 2025-01-07 03:25:06
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:53:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |         scanf("%d%d", &N, &P);
      |         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

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