제출 #540389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540389		levladiator	Sirni (COCI17_sirni)	C++14	0 / 140	5098 ms	311900 KiB

sirni

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define EPSILON 0.000001

using namespace std;

const ll NMAX = 1e5+5, INF = 1e18, MOD = 1e9+7, MMAX = 1e2 + 5, inf = INT_MAX;


ifstream fin("aleatoare.in");
ofstream fout("aleatoare.out");

int N,edges;
int par[NMAX],siz[NMAX];
map<int,int> M;
ll ans;

struct elem
{
    int val,ind;
};
elem v[NMAX];

int parent(int node)
{
    if(par[node]==node)return node;
    return(par[node]=parent(par[node]));
}

void dsu(int a,int b,int cost)
{
    a=parent(a);
    b=parent(b);
    if(a!=b)
    {
        if(siz[a]<siz[b])swap(a,b);
        siz[a]+=siz[b];
        par[b]=a;
        ans+=cost;
        edges++;
    }
}

bool cmp(elem a,elem b)
{
    if(a.val==b.val)return a.ind<b.ind;
    return a.val<b.val;
}

int main()
{
    cin.tie ( 0 )->sync_with_stdio ( 0 );
    cin.tie ( NULL );
    cout.tie ( NULL );

    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>v[i].val;
        if(!M[v[i].val])M[v[i].val]=i;
        v[i].ind=i;
        par[i]=i;
        siz[i]=1;
    }
    sort(v+1,v+N+1,cmp);
    for(int i=1;i<=N;i++)
    {
        if(v[i].val==v[i-1].val)dsu(v[i].ind,v[i-1].ind,0);
    }
    if(edges==N-1)
    {
        cout<<ans;
        return 0;
    }
    for(int cost=0;cost<=v[1].val;cost++)
    {
        for(int i=1;i<=N;i++)
        {
            if(v[i].val!=v[i-1].val)
            {
                for(int j=2*v[i].val;j<=v[N].val;j+=v[i].val)
                {
                    if(M[j+cost])
                    {
                        dsu(v[i].ind,M[j+cost],cost);
                        if(edges==N-1)
                        {
                            cout<<ans;
                            return 0;
                        }
                    }
                }
            }
        }
    }

    return 0;
}

• 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