# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
307540 | 2020-09-28T14:56:50 Z | luciocf | Sirni (COCI17_sirni) | C++14 | 5000 ms | 786436 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 main(void) { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a+1, a+n+1); vector<pii> V; for (int i = 1; i <= n; i++) for (int j = a[i]; j <= a[n]; j += a[i]) V.push_back({j, i}); sort(V.begin(), V.end()); set<pair<int, pii>> st; for (int i = 2; i <= n; i++) st.insert({a[i]-a[i-1], {i-1, i}}); int ptr = (int)V.size()-1; for (int i = n; i >= 1; i--) { while (ptr >= 0 && V[ptr].ff > a[i]) ptr--; while (ptr >= 0 && V[ptr].ff > a[i-1]) { st.insert({a[i]-V[ptr].ff, {i, V[ptr].ss}}); ptr--; } } dsu.init(n); ll ans = 0; for (auto pp: st) { 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); } } printf("%lld\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 768 KB | Output is correct |
2 | Correct | 2911 ms | 244248 KB | Output is correct |
3 | Correct | 9 ms | 2044 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1024 KB | Output is correct |
2 | Runtime error | 907 ms | 786432 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 768 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 5 ms | 1152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 715 ms | 84924 KB | Output is correct |
2 | Correct | 3268 ms | 420204 KB | Output is correct |
3 | Correct | 1736 ms | 208720 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 112 ms | 14304 KB | Output is correct |
2 | Execution timed out | 5106 ms | 513996 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1609 ms | 198552 KB | Output is correct |
2 | Execution timed out | 5115 ms | 704008 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 230 ms | 31432 KB | Output is correct |
2 | Execution timed out | 5100 ms | 694320 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1246 ms | 103208 KB | Output is correct |
2 | Execution timed out | 5091 ms | 527080 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1786 ms | 139296 KB | Output is correct |
2 | Runtime error | 940 ms | 786436 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 144 ms | 15204 KB | Output is correct |
2 | Execution timed out | 5085 ms | 526792 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |