oj.uz

Submission #540423

# Submission time Handle Problem Language Result Execution time Memory
540423 2022-03-20T10:29:36 Z levladiator Sirni (COCI17_sirni) C++14
112 / 140
 4879 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,maxi,maxcost;
int par[NMAX],siz[NMAX];
set<int> S;
ll ans;

struct edge
{
    int a,b;
};
vector<edge> edges[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;
    }
}

void kruskal()
{
    for(int i=0;i<=maxcost;i++)
    {
        for(auto x : edges[i])
        {
            int a=x.a;
            int b=x.b;
            dsu(a,b,i);
        }
    }
}

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;
        S.insert(x);
        par[x]=x;
        siz[x]=1;
        maxi=max(maxi,x);
    }
    for(auto x : S)
    {
        if(x==maxi)
        {
            bool ok=1;
        }
        auto it=S.upper_bound(x);
        int a=x;
        if(it!=S.end())
        {
            int b=*it;
            int cost=*it-x;
            edges[cost].pb({a,b});
            maxcost=max(maxcost,cost);
        }
        for(int j=2*x;j<=maxi;j+=x)
        {
            it=S.lower_bound(j);
            if(it!=S.end())
            {
                int b=*it;
                int cost=*it-j;
                edges[cost].pb({a,b});
                maxcost=max(maxcost,cost);
            }
        }
    }
    kruskal();
    cout<<ans;

    return 0;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:82:18: warning: unused variable 'ok' [-Wunused-variable]
   82 |             bool ok=1;
      |                  ^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 242564 KB Output is correct
2 Correct 379 ms 271784 KB Output is correct
3 Correct 122 ms 243348 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 235372 KB Output is correct
2 Runtime error 3667 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 130 ms 243196 KB Output is correct
2 Correct 141 ms 240176 KB Output is correct
3 Correct 125 ms 243232 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 257496 KB Output is correct
2 Correct 788 ms 286876 KB Output is correct
3 Correct 404 ms 268752 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 245756 KB Output is correct
2 Correct 329 ms 265788 KB Output is correct
3 Correct 307 ms 253144 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 270152 KB Output is correct
2 Correct 942 ms 305360 KB Output is correct
3 Correct 377 ms 266544 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 241812 KB Output is correct
2 Correct 832 ms 308032 KB Output is correct
3 Correct 367 ms 268688 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 331648 KB Output is correct
2 Correct 4486 ms 678032 KB Output is correct
3 Correct 461 ms 335340 KB Output is correct

Subtask #9
0 / 14.0

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

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 306784 KB Output is correct
2 Correct 4879 ms 683052 KB Output is correct
3 Correct 400 ms 268308 KB Output is correct