oj.uz

Submission #540389

# Submission time Handle Problem Language Result Execution time Memory
540389 2022-03-20T09:15:20 Z levladiator Sirni (COCI17_sirni) C++14
0 / 140
 5000 ms 311900 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];
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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5037 ms 276176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5060 ms 272792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5055 ms 48548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5098 ms 257264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5072 ms 311900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5032 ms 253728 KB Time limit exceeded
2 Halted 0 ms 0 KB -