Submission #1338312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338312		Nipphitch	Sirni (COCI17_sirni)	C++20	140 / 140	1557 ms	746968 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;

struct DSU{
    int p[N],sz[N];
    
    void build(){
        for(int i=0;i<N;i++) p[i]=i,sz[i];
    }

    int find_p(int u){
        return (u==p[u]?u:p[u]=find_p(p[u]));
    }

    bool same(int u,int v){
        return (find_p(u)==find_p(v));
    }

    void unite(int u,int v){
        u=find_p(u),v=find_p(v);
        if(u==v) return ;
        if(sz[u]<sz[v]) swap(u,v);
        sz[u]+=sz[v];
        p[v]=u;
    }

};

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    int mx=a.back();
    vector <int> nxt(mx+1,-1);
    for(int i=0;i<a.size();i++) nxt[a[i]]=i;
    for(int i=mx-1;i>=0;i--) if(nxt[i]==-1) nxt[i]=nxt[i+1];
    vector <vector <pair <int,int>>> edge(mx+1);
    for(int i=0;i<a.size()-1;i++){
        edge[a[i+1]%a[i]].push_back({i,i+1});
        for(int j=a[i]*2;j<=mx;j+=a[i]){
            int v=nxt[j];
            edge[a[v]%a[i]].push_back({i,v});
        }
    }
    long long mst=0;
    DSU dsu;
    dsu.build();
    for(int i=0;i<=mx;i++){
        for(auto [u,v]:edge[i]){
            if(dsu.same(u,v)) continue;
            dsu.unite(u,v);
            mst+=i;
        }
    }
    cout << mst;
}

• 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