結果
問題 | No.1917 LCMST |
ユーザー |
|
提出日時 | 2022-04-29 22:32:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,479 ms / 4,000 ms |
コード長 | 5,079 bytes |
コンパイル時間 | 2,211 ms |
コンパイル使用メモリ | 207,616 KB |
最終ジャッジ日時 | 2025-01-28 23:22:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < n; i++)#define rep2(i, x, n) for (int i = x; i <= n; i++)#define rep3(i, x, n) for (int i = x; i >= n; i--)#define each(e, v) for (auto &e : v)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;template <typename T>bool chmax(T &x, const T &y) {return (x < y) ? (x = y, true) : false;}template <typename T>bool chmin(T &x, const T &y) {return (x > y) ? (x = y, true) : false;}template <typename T>int flg(T x, int i) {return (x >> i) & 1;}template <typename T>void print(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');if (v.empty()) cout << '\n';}template <typename T>void printn(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << '\n';}template <typename T>int lb(const vector<T> &v, T x) {return lower_bound(begin(v), end(v), x) - begin(v);}template <typename T>int ub(const vector<T> &v, T x) {return upper_bound(begin(v), end(v), x) - begin(v);}template <typename T>void rearrange(vector<T> &v) {sort(begin(v), end(v));v.erase(unique(begin(v), end(v)), end(v));}template <typename T>vector<int> id_sort(const vector<T> &v, bool greater = false) {int n = v.size();vector<int> ret(n);iota(begin(ret), end(ret), 0);sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });return ret;}template <typename S, typename T>pair<S, T> operator+(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first + q.first, p.second + q.second);}template <typename S, typename T>pair<S, T> operator-(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first - q.first, p.second - q.second);}template <typename S, typename T>istream &operator>>(istream &is, pair<S, T> &p) {S a;T b;is >> a >> b;p = make_pair(a, b);return is;}template <typename S, typename T>ostream &operator<<(ostream &os, const pair<S, T> &p) {return os << p.first << ' ' << p.second;}struct io_setup {io_setup() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;const int inf = (1 << 30) - 1;const ll INF = (1LL << 60) - 1;const int MOD = 1000000007;// const int MOD = 998244353;struct Union_Find_Tree {vector<int> data;const int n;int cnt;Union_Find_Tree(int n) : data(n, -1), n(n), cnt(n) {}int root(int x) {if (data[x] < 0) return x;return data[x] = root(data[x]);}int operator[](int i) { return root(i); }bool unite(int x, int y) {x = root(x), y = root(y);if (x == y) return false;if (data[x] > data[y]) swap(x, y);data[x] += data[y], data[y] = x;cnt--;return true;}int size(int x) { return -data[root(x)]; }int count() { return cnt; };bool same(int x, int y) { return root(x) == root(y); }void clear() {cnt = n;fill(begin(data), end(data), -1);}};int main() {int N;cin >> N;int M = 100000;vector<int> cnt(M + 1, 0);rep(i, N) {int x;cin >> x;cnt[x]++;}ll ans = 0;rep(i, M + 1) {if (cnt[i] > 1) {ans += 1LL * i * (cnt[i] - 1);N -= cnt[i] - 1;cnt[i] = 1;}}vector<vector<int>> ids(M + 1);vector<vector<pii>> ds(M + 1);rep2(i, 1, M) {for (int j = i; j <= M; j += i) {if (cnt[j] > 0) {ds[j].eb(i, 0);ids[i].eb(j);}}}Union_Find_Tree uf(M + 1);vector<pli> tmp(M + 1, pli(INF, -1));vector<int> col(M + 1, -1);while (uf.count() > M - N + 2) {fill(all(tmp), pli(INF, -1));rep(i, M + 1) col[i] = uf[i];rep(i, M + 1) {if (cnt[i] == 0) continue;int u = col[i];pli mi = pli(INF, -1);rep(k, sz(ds[i])) {int e = ds[i][k].first;int &j = ds[i][k].second;while (j < sz(ids[e]) && col[ids[e][j]] == u) j++;if (j < sz(ids[e])) chmin(mi, pli(1LL * i * ids[e][j] / e, col[ids[e][j]]));}chmin(tmp[u], mi);}// vector<tuple<ll, int, int>> memo;rep(i, M + 1) {if (tmp[i].first < INF) {if (uf.unite(i, tmp[i].second)) ans += tmp[i].first;// memo.eb(tmp[i].first, i, tmp[i].second);// cout << tmp[i].first << ' ' << i << ' ' << tmp[i].second << '\n';}}}cout << ans << '\n';}