# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
307559 | 2020-09-28T15:28:35 Z | luciocf | Sirni (COCI17_sirni) | C++14 | 5000 ms | 762760 KB |
#include <bits/stdc++.h> #define ff first #define ss second using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5+10; const int maxv = 1e7+1; struct DSU { int pai[maxn], peso[maxn]; void init(int n) { for (int i = 1; i <= n; i++) pai[i] = i, peso[i] = 1; } int Find(int x) { if (pai[x] == x) return x; return pai[x] = Find(pai[x]); } void Join(int x, int y) { x = Find(x), y = Find(y); if (x == y) return; if (peso[x] < peso[y]) swap(x, y); pai[y] = x, peso[x] += peso[y]; } } dsu; int a[maxn]; int prim[maxv]; int main(void) { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a+1, a+n+1); int ptr = 2; for (int i = a[1]; i <= a[n]; i++) { while (ptr <= n && a[ptr] < i) ptr++; prim[i] = ptr; } int m = 0; dsu.init(n); set<pair<int, pii>> st; for (int i = 2; i <= n; i++) st.insert({a[i]-a[i-1], {i-1, i}}); for (int i = 1; i <= n; i++) { int j; for (j = i; j <= n && a[i] == a[j]; j++) if (j != i) dsu.Join(i, j), m++; i = j-1; for (int v = 2*a[i]; v <= a[n]; v += a[i]) st.insert({a[prim[v]]-v, {i, prim[v]}}); } ll ans = 0; for (auto pp: st) { if (m == n-1) break; int u = pp.ss.ff, v = pp.ss.ss, w = pp.ff; if (dsu.Find(u) != dsu.Find(v)) { ans += 1ll*w; dsu.Join(u, v), ++m; } } printf("%lld\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 39672 KB | Output is correct |
2 | Correct | 4847 ms | 213020 KB | Output is correct |
3 | Correct | 44 ms | 40696 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 896 KB | Output is correct |
2 | Execution timed out | 5117 ms | 762760 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 39672 KB | Output is correct |
2 | Correct | 36 ms | 39680 KB | Output is correct |
3 | Correct | 38 ms | 40056 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 669 ms | 71928 KB | Output is correct |
2 | Correct | 2826 ms | 268152 KB | Output is correct |
3 | Correct | 1317 ms | 143736 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 112 ms | 15736 KB | Output is correct |
2 | Correct | 3002 ms | 151960 KB | Output is correct |
3 | Correct | 622 ms | 71708 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1584 ms | 151672 KB | Output is correct |
2 | Correct | 3919 ms | 373912 KB | Output is correct |
3 | Correct | 1128 ms | 126456 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 199 ms | 24952 KB | Output is correct |
2 | Execution timed out | 5093 ms | 390544 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1294 ms | 124736 KB | Output is correct |
2 | Execution timed out | 5056 ms | 421880 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1764 ms | 156580 KB | Output is correct |
2 | Execution timed out | 5096 ms | 390128 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 183 ms | 51448 KB | Output is correct |
2 | Execution timed out | 5065 ms | 316984 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |