oj.uz

Submission #147733

# Submission time Handle Problem Language Result Execution time Memory
147733 2019-08-30T13:53:17 Z nicolaalexandra Sirni (COCI17_sirni) C++14
140 / 140
 3647 ms 307480 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#define DIM 100010
#define DIMM 10000010
using namespace std;
//ifstream cin ("date.in");
//ofstream cout ("date.out");
struct idk{
    int x,y,cost;
};
vector <idk> mch;
int n,i,j,k,last,maxi,nr;
int v[DIM],t[DIM],poz[DIMM],w[DIMM],ok[DIMM];

inline int cmp (idk a, idk b){
    return a.cost < b.cost;
}
inline int rad (int x){
    int nr = x;
    while (t[x] > 0)
        x = t[x];
    while (t[nr] > 0){
        int aux = t[nr];
        t[nr] = x;
        nr = aux;
    }
    return x;
}

int main (){

    cin>>n;
    for (i=1;i<=n;++i){
        cin>>v[i];
        maxi = max (maxi,v[i]);
    }
    sort (v+1,v+n+1);
    k = 1;
    for (i=2;i<=n;++i)
        if (v[i] != v[i-1]){
            v[++k] = v[i];
            poz[v[k]] = k;
        }
    n = k;
    int idx = n+1;
    for (i=maxi;i;--i){
        if (i == v[idx-1])
            idx--;
        w[i] = idx;
    }

    for (i=1;i<=n;++i){
        int last = i+1;
        if (i < n){
            int r = v[i+1]%v[i];
            mch.push_back({i,i+1,r});
        }
        if (ok[v[i]])
            continue;
        for (j=v[i]+v[i];j<=maxi;j+=v[i]){
            ok[j] = 1;
            if (poz[j]){ /// e in sir
                if (last != poz[j]){
                    int r = j%v[i];
                    mch.push_back({i,poz[j],r});
                    last = poz[j];
                }
            } else {
                int nr = w[j]; /// cea mai mica pozitie pe care se gaseste primul mai mare decat j
                if (last != nr){
                    int r = v[nr]%v[i];
                    mch.push_back({i,nr,r});
                    last = nr;
                }}}}
    sort (mch.begin(),mch.end(),cmp);
    for (i=1;i<=n;++i)
        t[i] = -1;
    long long sol = 0;
    for (int i=0;i<mch.size();++i){
        int x = mch[i].x, y = mch[i].y;
        int rx = rad(x), ry = rad(y);
        if (rx != ry){
            sol += mch[i].cost;
            if (t[rx] < t[ry]){
                t[rx] += t[ry];
                t[ry] = rx;
            } else {
                t[ry] += t[rx];
                t[rx] = ry;
            }}}
    cout<<sol;

    return 0;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<mch.size();++i){
                  ~^~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 57400 KB Output is correct
2 Correct 468 ms 83460 KB Output is correct
3 Correct 124 ms 79544 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 666 ms 79392 KB Output is correct
3 Correct 117 ms 82780 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 58612 KB Output is correct
2 Correct 79 ms 47480 KB Output is correct
3 Correct 101 ms 68344 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 25020 KB Output is correct
2 Correct 306 ms 37320 KB Output is correct
3 Correct 297 ms 37408 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 15312 KB Output is correct
2 Correct 320 ms 36440 KB Output is correct
3 Correct 164 ms 19032 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 37316 KB Output is correct
2 Correct 281 ms 37320 KB Output is correct
3 Correct 211 ms 24920 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 5996 KB Output is correct
2 Correct 287 ms 37164 KB Output is correct
3 Correct 235 ms 24964 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 142904 KB Output is correct
2 Correct 2050 ms 216828 KB Output is correct
3 Correct 572 ms 142924 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 142952 KB Output is correct
2 Correct 2540 ms 215916 KB Output is correct
3 Correct 715 ms 142844 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 116048 KB Output is correct
2 Correct 3647 ms 307480 KB Output is correct
3 Correct 267 ms 37192 KB Output is correct