# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
307558 | 2020-09-28T15:28:03 Z | luciocf | Sirni (COCI17_sirni) | C++14 | 32 ms | 3840 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; 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[maxn]; 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 | Runtime error | 4 ms | 3328 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 896 KB | Output is correct |
2 | Runtime error | 4 ms | 3584 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 3456 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 31 ms | 3576 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 7 ms | 3584 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 32 ms | 3576 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 20 ms | 3840 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 30 ms | 3584 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 30 ms | 3584 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 11 ms | 3616 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |