Submission #1245910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245910		nhatquang	Sirni (COCI17_sirni)	C++20	140 / 140	3962 ms	434720 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
struct dsu
{
    vector<int> par;
    void make(int n)
    {
        par.resize(n+4);
        for(int i=0;i<n;i++)
        par[i]=i;
    }
    int fs(int u)
    {
        return (par[u]==u) ? u : par[u]=fs(par[u]);
    }
    bool uns(int u,int v)
    {
        u=fs(u),v=fs(v);
        if(u==v) return false;
        par[v]=u;
        return true;
    }
};
struct edge
{
    int a,b,w;
};
int n,nx[10000004];
vector<edge> e;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin>>n;
    dsu g;
    g.make(n);
    vector<int> p;
    for(int x,i=1;i<=n;i++) cin>>x,p.push_back(x);
    sort(p.begin(),p.end());
    p.erase(unique(p.begin(),p.end()),p.end());
    n=p.size()-1;
    for(int i=0;i<n;i++)
    {
        nx[p[i]]=i;
        for(int j=p[i]+1;j<=p[i+1];j++)
            nx[j]=i+1;
    }
    for(int i=0;i<n;i++)
    {
        e.push_back({i,nx[p[i]+1],p[nx[p[i]+1]]%p[i]});
        for(int k=p[i]*2;k<=p[n];k+=p[i])
        {
            e.push_back({i,nx[k],p[nx[k]]%p[i]});
            k=p[nx[k]]/p[i]*p[i];
        }
    }
    sort(e.begin(),e.end(),[&](edge u,edge v){
        return u.w<v.w;
    });
    int ans=0;
    for(auto x:e)
    {
        if(!g.uns(x.a,x.b)) continue;
        ans+=x.w;
    }
    cout<<ans;
}

• 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