oj.uz

Submission #540401

# Submission time Handle Problem Language Result Execution time Memory
540401 2022-03-20T09:54:23 Z levladiator Sirni (COCI17_sirni) C++14
84 / 140
 2419 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 = 1e7+5, INF = 1e18, MOD = 1e9+7, MMAX = 1e2 + 5, inf = INT_MAX;


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

int N,nredges;
int par[NMAX],siz[NMAX];
vector<int> v;
ll ans;

struct edge
{
    int a,b,cost;
};
vector<edge> edges;

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;
    }
}

bool cmp(edge a, edge b)
{
    return a.cost<b.cost;
}

void kruskal()
{
    sort(edges.begin(),edges.end(),cmp);
    for(auto x : edges)
    {
        int a=x.a;
        int b=x.b;
        int cost=x.cost;
        dsu(a,b,cost);
    }
}

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

    cin>>N;
    for(int i=1;i<=N;i++)
    {
        int x;
        cin>>x;
        v.pb(x);
    }
    sort(v.begin(),v.end());
    int newN=0;
    for(int i=1;i<N;i++)
    {
        if(v[i]!=v[i-1])
        {
            v[++newN]=v[i];
            par[v[i]]=v[i];
            siz[v[i]]=1;
        }
    }
    N=newN;
    v.resize(N);
    for(int i=0;i<N;i++)
    {
        auto it=upper_bound(v.begin(),v.end(),v[i]);
        int a=v[i];
        int b=*it;
        int cost=*it-v[i];
        edges.pb({a,b,cost});
        for(int j=2*v[i];j<=v[N];j+=v[i])
        {
            it=lower_bound(v.begin(),v.end(),j);
            b=*it;
            cost=*it-j;
            edges.pb({a,b,cost});
        }
    }
    kruskal();
    cout<<ans;

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7764 KB Output is correct
2 Correct 363 ms 53668 KB Output is correct
3 Correct 8 ms 8596 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Runtime error 1065 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8276 KB Output is correct
2 Correct 4 ms 5336 KB Output is correct
3 Correct 5 ms 8532 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 33752 KB Output is correct
2 Correct 687 ms 58688 KB Output is correct
3 Correct 344 ms 58884 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11564 KB Output is correct
2 Correct 363 ms 56948 KB Output is correct
3 Correct 183 ms 30244 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 58340 KB Output is correct
2 Correct 929 ms 108180 KB Output is correct
3 Correct 283 ms 34160 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8388 KB Output is correct
2 Correct 958 ms 108080 KB Output is correct
3 Correct 308 ms 34240 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 104060 KB Output is correct
2 Runtime error 1848 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 104132 KB Output is correct
2 Runtime error 1669 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 72064 KB Output is correct
2 Runtime error 2419 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -