Submission #1262156

#TimeUsernameProblemLanguageResultExecution timeMemory
1262156khoile08Sirni (COCI17_sirni)C++20
140 / 140
1484 ms746588 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i = a; i <= b; i++) #define FOD(i,a,b) for(int i = a; i >= b; i--) //#define int long long #define fi first #define se second #define pb push_back #define ll long long #define ull unsigned long long #define db double #define lcm(a,b) a / __gcd(a, b) * b #define ii pair<int,int> #define iii pair<int,pair<int,int>> #define iv pair<pair<int,int>,pair<int,int>> #define sq(a) (a) * (a) #define MASK(i) (1LL << i) #define task "task" const int inf = 1e9; const ll INF = 1e18; const int mod = 1e9 + 7; const int N = 1e5 + 5; const int P = 1e7; int n; vector<int> a; int best[P + 5]; vector<ii> candi[P + 5]; int root[N], sze[N]; void init() { FOR(i, 0, (int)a.size() - 1) { root[i] = i; sze[i] = 1; } } int anc(int u) { return root[u] == u ? u : root[u] = anc(root[u]); } ll ans; void join(int u, int v, int w) { u = anc(u); v = anc(v); if(u == v) return; ans += w; if(sze[u] < sze[v]) swap(u, v); root[v] = u; sze[u] += sze[v]; } void KhoiLe() { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); int mx = a.back(); FOR(i, 1, mx) best[i] = -1; FOR(i, 0, (int)a.size() - 1) best[a[i]] = i; FOD(i, mx - 1, 1) if(best[i] == -1) best[i] = best[i + 1]; FOR(i, 0, (int)a.size() - 2) { candi[a[i + 1] % a[i]].pb({i, i + 1}); for(int j = 2 * a[i]; j <= mx; j += a[i]) { if(best[j] != -1) candi[a[best[j]] % a[i]].pb({i, best[j]}); } } init(); FOR(i, 0, mx) for(auto H : candi[i]) join(H.fi, H.se, i); cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int test = 1; // cin >> test; while(test--) { cin >> n; FOR(i, 1, n) { int x; cin >> x; a.pb(x); } KhoiLe(); } }
#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...