結果
問題 | No.1917 LCMST |
ユーザー | tnakao0123 |
提出日時 | 2022-04-30 23:11:28 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 442 ms / 4,000 ms |
コード長 | 2,365 bytes |
コンパイル時間 | 2,300 ms |
コンパイル使用メモリ | 59,476 KB |
実行使用メモリ | 51,272 KB |
最終ジャッジ日時 | 2023-09-12 14:57:03 |
合計ジャッジ時間 | 17,956 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
11,156 KB |
testcase_01 | AC | 3 ms
11,172 KB |
testcase_02 | AC | 3 ms
11,108 KB |
testcase_03 | AC | 5 ms
11,512 KB |
testcase_04 | AC | 6 ms
11,524 KB |
testcase_05 | AC | 6 ms
11,432 KB |
testcase_06 | AC | 6 ms
11,460 KB |
testcase_07 | AC | 6 ms
11,508 KB |
testcase_08 | AC | 3 ms
11,184 KB |
testcase_09 | AC | 417 ms
36,264 KB |
testcase_10 | AC | 422 ms
37,776 KB |
testcase_11 | AC | 419 ms
35,732 KB |
testcase_12 | AC | 398 ms
32,652 KB |
testcase_13 | AC | 279 ms
21,244 KB |
testcase_14 | AC | 408 ms
32,812 KB |
testcase_15 | AC | 235 ms
15,652 KB |
testcase_16 | AC | 283 ms
21,436 KB |
testcase_17 | AC | 322 ms
30,836 KB |
testcase_18 | AC | 359 ms
31,548 KB |
testcase_19 | AC | 224 ms
14,988 KB |
testcase_20 | AC | 205 ms
12,160 KB |
testcase_21 | AC | 232 ms
15,148 KB |
testcase_22 | AC | 205 ms
12,224 KB |
testcase_23 | AC | 207 ms
12,232 KB |
testcase_24 | AC | 228 ms
15,048 KB |
testcase_25 | AC | 208 ms
12,264 KB |
testcase_26 | AC | 214 ms
12,744 KB |
testcase_27 | AC | 219 ms
14,756 KB |
testcase_28 | AC | 224 ms
14,840 KB |
testcase_29 | AC | 437 ms
49,848 KB |
testcase_30 | AC | 439 ms
49,808 KB |
testcase_31 | AC | 440 ms
49,756 KB |
testcase_32 | AC | 437 ms
51,192 KB |
testcase_33 | AC | 442 ms
49,816 KB |
testcase_34 | AC | 124 ms
9,244 KB |
testcase_35 | AC | 124 ms
9,336 KB |
testcase_36 | AC | 124 ms
9,316 KB |
testcase_37 | AC | 435 ms
49,692 KB |
testcase_38 | AC | 434 ms
51,264 KB |
testcase_39 | AC | 442 ms
49,868 KB |
testcase_40 | AC | 435 ms
49,832 KB |
testcase_41 | AC | 434 ms
51,272 KB |
testcase_42 | AC | 441 ms
49,844 KB |
testcase_43 | AC | 126 ms
15,136 KB |
testcase_44 | AC | 127 ms
15,148 KB |
ソースコード
/* -*- coding: utf-8 -*- * * 1917.cc: No.1917 LCMST - yukicoder */ #include<cstdio> #include<vector> #include<algorithm> using namespace std; /* constant */ const int MAX_N = 1000000; const int MAX_A = 100000; /* typedef */ typedef long long ll; typedef vector<int> vi; struct Edge { int u, v; ll w; Edge() {} Edge(int _u, int _v, ll _w): u(_u), v(_v), w(_w) {} bool operator<(const Edge &e) const { return w < e.w; } }; typedef vector<Edge> ve; struct UFT { int links[MAX_N], ranks[MAX_N], sizes[MAX_N]; UFT() {} void init(int n) { for (int i = 0; i < n; i++) links[i] = i, ranks[i] = sizes[i] = 1; } int root(int i) { int i0 = i; while (links[i0] != i0) i0 = links[i0]; return (links[i] = i0); } int rank(int i) { return ranks[root(i)]; } int size(int i) { return sizes[root(i)]; } bool same(int i, int j) { return root(i) == root(j); } int merge(int i0, int i1) { int r0 = root(i0), r1 = root(i1), mr; if (r0 == r1) return r0; if (ranks[r0] == ranks[r1]) { links[r1] = r0; sizes[r0] += sizes[r1]; ranks[r0]++; mr = r0; } else if (ranks[r0] > ranks[r1]) { links[r1] = r0; sizes[r0] += sizes[r1]; mr = r0; } else { links[r0] = r1; sizes[r1] += sizes[r0]; mr = r1; } return mr; } }; /* global variables */ int as[MAX_N]; vi vs[MAX_A + 1]; UFT uft; /* subroutines */ /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", as + i); sort(as, as + n); ll sum = 0; int k = 0; for (int i = 0; i < n;) { int j = i; while (i < n && as[j] == as[i]) i++; as[k++] = as[j]; sum += (ll)as[j] * (i - j - 1); } for (int i = 0; i < k; i++) { int ai = as[i]; for (int p = 1; p * p <= ai; p++) if (ai % p == 0) { vs[p].push_back(i); int q = ai / p; if (q != p) vs[q].push_back(i); } } int maxa = as[k - 1]; ve es; for (int d = 1; d <= maxa; d++) { vi &vd = vs[d]; if (vd.size() > 1) { int u = vd[0]; for (int i = 1; i < vd.size(); i++) es.push_back(Edge(u, vd[i], (ll)as[u] * as[vd[i]] / d)); } } sort(es.begin(), es.end()); uft.init(k); for (auto e: es) if (! uft.same(e.u, e.v)) { uft.merge(e.u, e.v); sum += e.w; } printf("%lld\n", sum); return 0; }