Submission #1174243

#TimeUsernameProblemLanguageResultExecution timeMemory
1174243InvMODSirni (COCI17_sirni)C++20
140 / 140
3566 ms198284 KiB
#include<bits/stdc++.h> using namespace std; #define sz(v) (v).size() #define all(v) (v).begin(), (v).end() #define compact(v) (v).erase(unique(all(v)), (v).end()) using ll = long long; const int N = 1e5; int n, i, p, nxt, par[N], answer; int asc(int x){ return par[x] < 0 ? x : par[x] = asc(par[x]); } void join(int u, int v, int w){ u = asc(u), v = asc(v); if(u != v){ answer += w; par[u] = v; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; vector<int> a(n); for(i = 0; i < n; i++){ cin >> a[i]; par[i] = -1; } sort(all(a)), compact(a); vector<pair<int, pair<int,int>>> E; for(i = sz(a) - 1; i >= 0; i--){ nxt = a[i], p = lower_bound(1 + i + all(a), nxt) - a.begin(); while(p < sz(a)){ if(a[p] % a[i] < a[0]) E.push_back(make_pair(a[p] % a[i], make_pair(i, p))); nxt += a[i]; p = lower_bound(1 + i + all(a), nxt) - a.begin(); } } sort(all(E)); for(auto i : E){ join(i.second.first, i.second.second, i.first); } cout << answer << "\n"; 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...