oj.uz

답안 #147595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
147595 2019-08-30T08:43:38 Z nicolaalexandra Sirni (COCI17_sirni) C++14
0 / 140
 5000 ms 7756 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#define DIM 100010
using namespace std;
//ifstream fin ("date.in");
//ofstream fout ("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[DIM];

inline int cmp (idk a, idk b){
    return a.cost < b.cost;
}
inline int rad (int x){
    while (t[x] > 0)
        x = t[x];
    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];
    for (i=1;i<=n;i++)
        poz[v[i]] = i;
    n = k;
    for (i=1;i<=n;i++){
        int last = i+1;
        if (i < n){
            int r = min (v[i]%v[i+1],v[i+1]%v[i]);
            mch.push_back({i,i+1,r});
        }
        for (j=v[i]+v[i];j<=maxi;j+=v[i]){
            if (poz[j]){ /// e in sir
                if (last != poz[j]){
                    int r = min (v[i]%j,j%v[i]);
                    mch.push_back({i,poz[j],r});
                    last = poz[j];
                }
            } else {
                int st = 1, dr = n, val = j;
                while (st <= dr){
                    int mid = (st+dr)>>1;
                    if (v[mid] >= val){
                        dr = mid-1;
                        nr = mid;
                    } else st = mid+1;
                }
                if (last != nr){
                    int r = min (v[i]%v[nr],v[nr]%v[i]);
                    mch.push_back({i,nr,r});
                    last = nr;
                }}}}
    sort (mch.begin(),mch.end(),cmp);
    int 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:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<mch.size();i++){
                  ~^~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 69 ms 3548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 68 ms 3524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5053 ms 7756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 74 ms 3580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 75 ms 3736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 2680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -