Submission #1191350

#TimeUsernameProblemLanguageResultExecution timeMemory
1191350oguzhan09Sirni (COCI17_sirni)C++20
42 / 140
985 ms851968 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int parent[MAXN]; int find(int x) { if (parent[x] == x) return x; return parent[x] = find(parent[x]); } bool unite(int a, int b) { int pa = find(a); int pb = find(b); if (pa == pb) return false; parent[pa] = pb; return true; } int main() { int n; cin >> n; vector<int> p(n); for (int i = 0; i < n;i++) cin >> p[i]; vector<tuple<int, int, int>> edges; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n;j++) { int cost = min(p[i] % p[j], p[j] % p[i]); edges.emplace_back(cost, i, j); } } sort(edges.begin(), edges.end()); for (int i = 0; i < n; ++i) parent[i] = i; long long total = 0; int count = 0; for (auto [cost, u, v] : edges) { if (unite(u, v)) { total += cost; count++; if (count == n - 1) break; } } cout << total << endl; }
#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...