Submission #990124

#TimeUsernameProblemLanguageResultExecution timeMemory
990124SkaSirni (COCI17_sirni)C++14
0 / 140
8 ms860 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n; int a[N]; struct { int e[N]; void reset() { fill(e + 1, e + n + 1, -1); } int find(int u) { if (e[u] < 0) { return u; } return e[u] = find(e[u]); } bool join(int u, int v) { u = find(u); v = find(v); if (u == v) { return false; } if (e[u] > e[v]) { swap(u, v); } e[u] += e[v]; e[v] = u; return true; } } dsu; namespace sub1 { vector<pair<int, int>> edges; int calc(int i, int j) { return min(a[i] % a[j], a[j] % a[i]); } void solve() { dsu.reset(); for (int i = 1; i < n; ++i) { int f1 = -1, f2 = -1; for (int j = i + 1; j <= n; ++j) { int val = calc(i, j); int k = j; if (f1 == -1 || val <= calc(i, f1)) { swap(k, f1); } if (f2 == -1 || val <= calc(i, f2)) { swap(k, f2); } } edges.emplace_back(i, f1); if (f2 > 0) { edges.emplace_back(i, f2); } } sort(edges.begin(), edges.end(), [&](pair<int, int> x, pair<int, int> y) { return (calc(x.first, x.second) < calc(x.first, x.second)); }); int cnt = 0; long long res = 0; for (auto x : edges) { int u = x.first, v = x.second; if (dsu.join(u, v)) { ++cnt; res += calc(u, v); } if (cnt == n - 1) { break; } } assert(cnt == n - 1); cout << res << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; } if (n <= 1000) { sub1::solve(); } }
#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...