Submission #1190898

#TimeUsernameProblemLanguageResultExecution timeMemory
1190898vusalSirni (COCI17_sirni)C++20
42 / 140
1010 ms851968 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int oo = 1e18; const int MAXN = 1e5 + 7; int par[MAXN]; int sz[MAXN]; int getl(int x) { if(par[x] == -1) return x; return par[x] = getl(par[x]); } bool unite(int a, int b) { a = getl(a); b = getl(b); if(a == b) return false; if(sz[a] > sz[b]) swap(a, b); sz[b] += sz[a]; par[a] = b; return true; } void _() { int n; cin >> n; vector<int>v(n); for(int &i : v) cin >> i; vector<array<int,3>>q; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { q.push_back({min(v[i] % v[j], v[j] % v[i]), i, j}); } } sort(q.begin(), q.end()); int sum = 0; for(auto [w, u, v] : q) { if(unite(u, v)) { sum += w; } } cout << sum << endl; } signed main() { fill(par, par + MAXN, -1); fill(sz, sz + MAXN, 1); int tt = 1; // cin >> tt; while(tt--) _(); }
#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...