Submission #156114

#	Time	Username	Problem	Language	Result	Execution time	Memory
156114		ionanghelina	Sirni (COCI17_sirni)	C++14	0 / 140	309 ms	46400 KiB

sirni

#include<bits/stdc++.h>
using namespace std;

const int maxN=(1e5)+5;
const int maxV=(1e7)+5;
const int inf=INT_MAX;

struct tip
{
    int x,y,cost;

    bool operator<(const tip& other)
    {
        return cost<other.cost;
    }
};
 int t[maxN];

inline int getRoot(int x)
        {
            //getting the root
            int y=x;

            while(t[y]>0) y=t[y];

            //road compression
            int z=y;

            y=x;

            while(y!=z)
            {
                int aux=t[y];
                t[y]=z;
                y=aux;
            }

            return y;
        }

inline void unite(int x,int y)
        {
            int tx=getRoot(x);
            int ty=getRoot(y);
            if(tx<ty)
            {
                t[tx]+=t[ty];
                t[ty]=tx;
            }
                else
            {
                t[ty]+=t[tx];
                t[tx]=ty;
            }
        }
vector<tip> edges;

int n,v[maxN],cnt,M[maxV],nrm[maxN],x,y,cst,tx,ty;
long long sol;


inline int cost(int x,int y)
{
    int xa,ya;

    xa=M[x];
    ya=M[y];
    return min((xa%ya),(ya%xa));

}
int taken=0;

inline int bs1(int x)
{
    int sol=0;
    for(int step=(1<<20);step;step>>=1)
        if((sol+step)<=n && v[sol+step]<=x) sol+=step;
    return sol+1;
}
inline int bs2(int x)
{
    int sol=0;
    for(int step=(1<<20);step;step>>=1)
        if((sol+step)<=n && v[sol+step]<x) sol+=step;
    return sol+1;
}

bool in[maxV],seen[maxV];
vector<int> w;

int main()
{
   // freopen("sirni.in","r",stdin);
   // freopen("sirni.out","w",stdout);

    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        in[v[i]]=1;
    }

    sort(v+1,v+n+1);

    v[n+1]=inf;


    for(int i=2;i<=10000000;i++)
    {
        if(!in[i]) continue;
        if(seen[i]) continue;
        x=i;
        for(int j=x+x;j<=10000000;j+=x)
            seen[j]=1;

    }

    for(int i=1;i<=n;i++)
    {
        if(!seen[v[i]]) w.push_back(v[i]);
    }
    n=0;
    for(auto it:w) v[++n]=it;

    for(int i=1;i<=n;i++)
    {
        if(i==1 || v[i]!=v[i-1]) cnt++;
        M[cnt]=v[i];
        nrm[i]=cnt;
    }


    for(int i=1;i<=cnt;i++)
    {
//        if(seen[M[i]]) continue;
        int x=M[i];
        if(x>=v[n]) continue;

        int ind=bs1(x);



        edges.push_back({i,nrm[ind],cost(i,nrm[ind])});
        int lst=nrm[ind];

        for(int j=x+x;j<=v[n];j+=x)
        {
            if(j>v[n]) continue;

            ind=bs2(j);

            if(nrm[ind]!=lst) edges.push_back({i,nrm[ind],cost(i,nrm[ind])});
            lst=nrm[ind];
        }
    }



    sort(edges.begin(),edges.end());

    //for(auto it:edges)
      //  printf("%d %d% d\n",it.x,it.y,it.cost);



    for(int i=1;i<=cnt;i++)
            t[i]=-1;

    for(auto it:edges)
    {
        if(taken==cnt-1) break;
        x=it.x;
        y=it.y;
        cst=it.cost;

        tx=getRoot(x);
        ty=getRoot(y);

        if(tx!=ty)
        {
            taken++;
            sol+=1LL*cst;
            unite(tx,ty);
        }
    }


    printf("%lld\n",sol);

    return 0;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
sirni.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&v[i]);
         ~~~~~^~~~~~~~~~~~

• 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