oj.uz

답안 #1106945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106945 2024-10-31T09:37:23 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 3066 ms 452332 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int nmax = 1e7 + 1;
using ll = long long;
int n;

vector<int> v;
int root[nmax + 5];
int nxt[nmax + 5];

struct tt{
    int x;
    int y;
    int z;
};

vector<tt> edge;

bool cmp(tt x, tt y){
    return x.z < y.z;
}

int find(int u) { return (u == root[u] ? u : root[u] = find(root[u])); }


signed main(){
    cin>>n;
    for(int i = 1 , x ; i <= n ; ++i){
        cin>>x;
        v.push_back(x);

    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int j = 0;
    for(int i = 1 ; i <= v.back() ; ++i){
        while(i > v[j] ) j++;
        nxt[i] = v[j];
    }


    for (int x : v) for (int y = x; y <= v.back(); y += x) {
        int p = nxt[(y==x?y+1:y)];
        if (!p) break;
        if (y + x < p) y = (p - y) / x * x + y;
        edge.push_back({x, p, p - y});
    }

    for(auto i : v) root[i] = i;

    sort(edge.begin(),edge.end(),cmp);
    ll ans = 0;
    for (tt ee : edge) {
        int u = ee.x, v = ee.y, c = ee.z;
        //cout<<u<<'.'<<v<<'.'<<c<<"\n";
        u = find(u), v = find(v);
        if (u != v) {
            root[u] = v;
            ans += 1ll*c;
        }
  }
  cout << ans;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 78672 KB Output is correct
2 Correct 43 ms 80928 KB Output is correct
3 Correct 17 ms 78652 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 22 ms 79364 KB Output is correct
3 Correct 20 ms 78644 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 78672 KB Output is correct
2 Correct 13 ms 70272 KB Output is correct
3 Correct 17 ms 78672 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 23792 KB Output is correct
2 Correct 301 ms 58644 KB Output is correct
3 Correct 130 ms 32184 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 13040 KB Output is correct
2 Correct 214 ms 56620 KB Output is correct
3 Correct 118 ms 19676 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 56616 KB Output is correct
2 Correct 400 ms 106020 KB Output is correct
3 Correct 124 ms 32132 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 13112 KB Output is correct
2 Correct 388 ms 106008 KB Output is correct
3 Correct 151 ms 32036 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 93668 KB Output is correct
2 Correct 2079 ms 436220 KB Output is correct
3 Correct 191 ms 97748 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 93668 KB Output is correct
2 Correct 2989 ms 452332 KB Output is correct
3 Correct 216 ms 103964 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 80896 KB Output is correct
2 Correct 3066 ms 448240 KB Output is correct
3 Correct 142 ms 32100 KB Output is correct