oj.uz

Submission #540387

# Submission time Handle Problem Language Result Execution time Memory
540387 2022-03-20T09:08:08 Z levladiator Sirni (COCI17_sirni) C++14
0 / 140
 1819 ms 786432 KB 
#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];
set<int> S[100*NMAX];
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;
        S[v[i].val].insert(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)
                {
                    for(auto x : S[j+cost])
                    {
                        dsu(v[i].ind,x,cost);
                        if(edges==N-1)
                        {
                            cout<<ans;
                            return 0;
                        }
                    }
                }
            }
        }
    }

    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1651 ms 786432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 254 ms 470080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1100 ms 786432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 520 ms 476872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 471092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 748 ms 476928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 472640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1656 ms 477036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 675 ms 477036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1819 ms 471480 KB Output isn't correct
2 Halted 0 ms 0 KB -