Submission #863166

#TimeUsernameProblemLanguageResultExecution timeMemory
863166MisterReaperSirni (COCI17_sirni)C++17
140 / 140
2980 ms538612 KiB
//author: Ahmet Alp Orakci #include <bits/stdc++.h> using namespace std; using i64 = long long; const int MAXN = 1E7 + 5; ostream& operator<< (ostream& os, pair <int, int> &pii) { return os << "{" << pii.first << " " << pii.second << "}"; } struct DSU { int n; vector <int> par; DSU(int n) : n(n) { par.resize(n); iota(par.begin(), par.end(), 0); } inline int get(int x) { return par[x] = (x == par[x] ? x : get(par[x])); } inline bool same(int a, int b) { return get(a) == get(b); } inline bool unite(int u, int v) { if(same(u, v)) return false; u = get(u); v = get(v); par[v] = u; return true; } }; vector <pair <int, int>> edges[MAXN]; #define ONLINE_JUDGE void solve() { int n; cin >> n; vector <int> vec(n); for(int &i : vec) cin >> i; sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); if(vec.front() == 1) return cout << 0, void(); n = vec.size(); for(int it = 0; it < n -1; it++) { int i = vec[it]; for(int k = i; k < MAXN; k += i) { int x = upper_bound(vec.begin() + it + 1, vec.end(), k -1) - vec.begin(); if(x < n && k <= vec[x] && vec[x] < k + i) edges[vec[x] - k].emplace_back(it, x); } } i64 ans = 0; DSU dsu(n); for(int i = 0; i < MAXN; i++) { for(auto [u, v] : edges[i]) { if(dsu.unite(u, v)) { ans += i; } } } cout << ans; return; } signed main() { #ifndef ONLINE_JUDGE freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin >> t; for(int i = 1; i <= t; i++) { solve(); } 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...