Submission #982964

#TimeUsernameProblemLanguageResultExecution timeMemory
982964ndanSirni (COCI17_sirni)C++14
140 / 140
3697 ms399820 KiB
// Practice makes perfect #include <bits/stdc++.h> #include <set> using namespace std; #define fastIO ios_base::sync_with_stdio(0); cin.tie(0); #define file "" #define ll long long const int maxn = 1e5 + 5; int n, p[maxn], lab[maxn]; set<int> s; ll ans = 0; struct Edge { int u, v, w; bool operator < (Edge &e) { return w < e.w; } }; vector<Edge> edges; int Find(int u) { return lab[u] < 0 ? u : lab[u] = Find(lab[u]); } bool unite(int a, int b) { a = Find(a); b = Find(b); if (a == b) return 0; if (lab[a] > lab[b]) swap(a, b); lab[a] += lab[b]; lab[b] = a; return 1; } int main() { fastIO //freopen(file".inp", "r", stdin); //freopen(file".out", "w", stdout); cin >> n; for (int i = 0; i < n; ++i) { int x; cin >> x; s.insert(x); } vector<int> v = vector<int>(s.begin(), s.end()); if (v[0] == 1 || v.size() == 1) { cout << 0; return 0; } for (int i = 0; i < n; ++i) lab[i] = -1; n = v.size(); int mx = v[n - 1]; for (int i = 0; i < n; ++i) { int j = i; for (int val = v[i]; val <= mx; val += v[i]) { int last = j; while (j + 1 < n && v[j] < val) j++; if (v[j] == v[i]) j++; if (j != n && last != j) { Edge e; e.u = i; e.v = j; e.w = v[j] % v[i]; edges.push_back(e); } } } sort(edges.begin(), edges.end()); for (Edge &e : edges) if (unite(e.u, e.v)) ans += e.w; cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...