Submission #701007

#	Time	Username	Problem	Language	Result	Execution time	Memory
701007		amin	Sirni (COCI17_sirni)	C++14	0 / 140	451 ms	407704 KiB

sirni

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define rep(i,a,b) for(i=a;i<b;i++)
int nex[10000002];
int sz[10000002],vis[10000002];
int p[20000000];
ll ans=0;
int par(int x)
{
    if(p[x]==x)
    return x;
    p[x]=par(p[x]);
    return p[x];
}
void un(int x,int y,int cost)
{
    x=par(x);
    y=par(y);
    if(x==y)
    {
        return ;
    }
    ans+=cost;
if(sz[x]<sz[y])
{
    swap(x,y);
}
sz[x]+=sz[y];
sz[y]=0;
p[y]=x;
}

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        p[a[i]]=a[i];
        nex[a[i]]=a[i];
    }
    for(int i=10000000;i>=0;i--)
    {
        if(nex[i]==i)
        {
            continue;
        }
        nex[i]=nex[i+1];
    }
   vector<pair<int,int> >v[10000000];
    for(int i=1;i<=1e7;i++)
    {
        if(nex[i]==i&&vis[i]==0)
        {
            vis[i]=1;
            for(int y=i;y<=1e7;y+=i)
            {
                vis[y]=1;
                if(nex[y+1]!=0)
                v[nex[y+1]%i].push_back({i,nex[y+1]});
            }
        }
    }
    for(int i=0;i<1e7;i++)
    {
        for(auto y:v[i])
        {
            un(y.first,y.second,i);
        }
    }
    cout<<ans;

}

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