Submission #1265598

#TimeUsernameProblemLanguageResultExecution timeMemory
1265598nguyenhuythachSirni (COCI17_sirni)C++20
0 / 140
17 ms24328 KiB
#include<bits/stdc++.h> #include<algorithm> #include<random> #include<chrono> #include<cstdlib> #include<ctime> #include<numeric> #include<vector> #include<stack> #include<map> #include<set> #include<queue> #include<iomanip> #define int long long #define ll long long #define L LLONG_MAX #define fi first #define se second #define pii pair<int,int> #define sz(a) ((int)a.size()) #define FOR(i,j,k) for(int i=j;i<=k;i++) #define REP(i,k,j) for(int i=k;i>=j;i--) #define FORD(i,a) for(auto i:a) #define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) #define random(l,r) ((l)+(rng()%(r-l+1))) using namespace std; struct triple { int u,v,w; }; const int nmax=1e5+69; int n,mx=0; vector<pii> p; vector<triple> edge; bool cnt[nmax]; void input() { cin >> n; FOR(i,1,n) { int x; cin >> x; if(!cnt[x]) p.push_back({x,i}); cnt[x]=true; mx=max(mx,x); } } void counting_sort() { // FORD(i,edge) cout << i.u << ' ' << i.v << ' ' << i.w << '\n'; vector<triple> save[1000001]; FORD(i,edge) save[i.w].push_back(i); edge.clear(); FOR(i,0,1e6) FORD(j,save[i]) edge.push_back(j); } struct DSU { vector<int> par; DSU() {} void init(int n) { par.resize(n+5,0); FOR(i,1,n) par[i]=i; } int find(int v) { if(v==par[v]) return v; return par[v]=find(par[v]); } bool joint(int u,int v) { u=find(u); v=find(v); if(u!=v) { par[v]=u; return true; } return false; } }; DSU dsu; void solve() { dsu.init(n); sort(p.begin(),p.end()); FORD(i,p) { for(int j=i.fi;j<=mx;j+=i.fi) { auto it=lower_bound(p.begin(),p.end(),make_pair(j,1ll*0)); if(it!=p.end()) edge.push_back({i.se,(*it).se,(*it).fi%i.fi}); } } counting_sort(); int ans=0; FORD(i,edge) ans+=dsu.joint(i.u,i.v)*i.w; cout << ans; } signed main() { //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); input(); solve(); }
#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...