結果
問題 | No.1059 素敵な集合 |
ユーザー |
|
提出日時 | 2020-04-28 17:34:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 1,850 bytes |
コンパイル時間 | 800 ms |
コンパイル使用メモリ | 75,380 KB |
最終ジャッジ日時 | 2025-01-10 02:42:15 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream> #include <numeric> #include <vector> /* まずLからRの頂点R-L+1個からなるグラフを考える. 操作中に消すペアを辺で結ぶと,最終的に全域木ができる. 一方,全域木について葉から順に消すことで最終的にシングルトンになる操作が得られる. 従ってこの問題は,「LからRの頂点からなり,頂点u, v間にmin(u % v, v % u)の重みの辺を 張ったグラフの最小全域木のコストを求めよ」という問題と同値となる. これをクラスカル法で解く. まず重み0の辺,つまりu|vなるu, vは貪欲に結んでよい. これを終えた後の連結成分数をgとしたとき,答えはg-1となる. これは,任意のu<Rについて(u+1)%u=1であることから従う. */ struct UnionFind { std::vector<int> par, sz; explicit UnionFind(int n) : par(n), sz(n, 1) { std::iota(par.begin(), par.end(), 0); } int find(int v) { return (par[v] == v) ? v : (par[v] = find(par[v])); } void unite(int u, int v) { u = find(u), v = find(v); if (u == v) return; if (sz[u] < sz[v]) std::swap(u, v); sz[u] += sz[v]; par[v] = u; } bool same(int u, int v) { return find(u) == find(v); } }; int main() { int l, r; std::cin >> l >> r; UnionFind uf(r + 1); // x|yなるx, y間に辺を張る(コスト0) for (int x = l; x <= r; ++x) { for (int y = x * 2; y <= r; y += x) { uf.unite(x, y); } } int ans = 0; // x, x+1間に辺を張る(コスト1) for (int x = l; x + 1 <= r; ++x) { if (!uf.same(x, x + 1)) { ++ans; uf.unite(x, x + 1); } } std::cout << ans << std::endl; return 0; }