Submission #1191476

#TimeUsernameProblemLanguageResultExecution timeMemory
1191476TheSahibSirni (COCI17_sirni)C++17
14 / 140
299 ms326224 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define all(v) v.begin(), v.end() #define pii pair<int, int> const int MAX = 1e7 + 100, MOD = 1e9 + 7, oo = 1e18; int par[MAX],sz[MAX]; int get(int a){ if(par[a]==-1)return a; return par[a]=get(par[a]); } bool unite(int a,int b){ a=get(a); b=get(b); if(a==b)return false; if(sz[a]>sz[b])swap(a,b); sz[b]+=sz[a]; par[a]=b; return true; } vector<array<int, 2>> edges[MAX]; int lb[MAX]; void solve(){ memset(par, -1, sizeof(par)); int n; cin >> n; vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; sz[i] = 1; } sort(all(v)); v.erase(unique(all(v)), v.end()); lb[v[n - 1]] = n - 1; for(int i = v[n - 1] - 1; i >= 0; --i){ if(lb[i + 1] == 0){ lb[i] = 0; continue; } if(v[lb[i + 1] - 1] >= i) lb[i] = lb[i + 1] - 1; else lb[i] = lb[i + 1]; } for (int i = 0; i < v.size() - 1; i++) { int x = v[i]; edges[v[i + 1] % v[i]].push_back({i, i + 1}); for(int l = x * 2; l <= v[n - 1]; ){ int j = lb[l]; edges[v[j] % v[i]].push_back({i, j}); l = (v[j] / x + 1) * x; } } long long ans = 0; for(int c = 0; c < MAX; ++c){ for(auto& e:edges[c]){ if(unite(e[0], e[1])){ ans += c; } } } cout << ans << '\n'; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while(t--){ solve(); } }

Compilation message (stderr)

sirni.cpp:10:48: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   10 | const int MAX = 1e7 + 100, MOD = 1e9 + 7, oo = 1e18;
      |                                                ^~~~
#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...