제출 #1154518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154518		sitablechair	Sirni (COCI17_sirni)	C++20	140 / 140	1632 ms	746344 KiB

sirni

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);


const int N=1e5+3;

using namespace std;

int n,a[N],g[N*100],f[N],m;
vector<pair<int,int>> mmb[N*100];
vector<int> aa;
ll ans=0;
int find_set(int x) {
    return (f[x]<0?x:f[x]=find_set(f[x]));
}
void unite(int u,int v,ll w) {
    int a=find_set(u),b=find_set(v);
    if (a==b) return;
    m--;
    ans+=w;
    if (f[a]>f[b]) swap(a,b);
    f[a]+=f[b];
    f[b]=a;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    For(i,1,n) {
        int x;
        cin >> x;
        aa.pb(x);
    }
    sort(all(aa));
    unq(aa);
    n=sz(aa);
    For(i,1,n) a[i]=aa[i-1];
    m=n;
    fill(g,g+10000001,-1);
    fill(f,f+1+n,-1);
    For(i,1,1e7) {
        g[i]=g[i-1];
        if (g[i]<n && i>=a[g[i]+1]) g[i]++;
    }
    For(i,1,n)
        for(int j=a[i];j<=1e7;j+=a[i])
            if (a[g[j]]==j && j>a[i]) mmb[0].pb({i,g[j]});
            else if (g[j]+1<=n) mmb[a[g[j]+1]%a[i]].pb({g[j]+1,i});
    For(i,0,1e7) {
        for(auto el: mmb[i]) {
            unite(el.ff,el.ss,i);
        }
        if (m==1) break;
    }
    cout << ans;
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14