제출 #1317748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317748		anarch_y	Sirni (COCI17_sirni)	C++20	112 / 140	5114 ms	824028 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

struct DSU{
    vector<int> link, size;
    int cc;
 
    DSU(int n){
        link.resize(n+1, 0);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) link[i] = i;
        cc = n;
    }
 
    int find(int x){
        if(x != link[x]) link[x] = find(link[x]);
        return link[x];
    }
 
    bool same(int a, int b){
        return find(a) == find(b);
    }
    
    void merge(int a, int b){
        if(same(a, b)) return;
        a = find(a); b = find(b);
        if(size[a] > size[b]) swap(a, b);
        link[a] = b;
        size[b] += size[a];
        cc--;
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<int> v(1e7+1);
    int m = 0;
    for(int i=1; i<=n; i++){
        int x; cin >> x;
        v[x] = 1;
        m = max(m, x);
    }
    vector<int> mp(m+1);
    int c = 0;
    for(int i=1; i<=m; i++){
        if(v[i] == 1){
            mp[i] = ++c;
        }
    }
    n = c;
    DSU D(n);
    for(int i=1; i<=m; i++){
        if(v[i] == 1){
            for(int j=2*i; j<=m; j+=i){
                if(v[j] == 1){
                    D.merge(mp[i], mp[j]);
                }
            }
        }
    }
    vector<int> w[m+1];
    for(int i=1; i<=m; i++){
        if(v[i] == 1){
            w[i].pb(i);
            for(int j=2*i; j<=m; j+=i){
                if(v[j] == 0) v[j] = 2;
                w[j].pb(i);
            }
        }
    }
    vector<int> p(m+1);
    c = 0;
    for(int i=1; i<=m; i++){
        if(v[i] == 0) continue;
        p[i] = c;
        c = i;
    }
    vector<array<int, 3>> vec;
    using T = array<int, 3>;
    priority_queue<T, vector<T>, greater<T>> pq;
    for(int i=1; i<=m; i++){
        if(v[i] == 1){
            int j = p[i];
            if(j == 0) continue;
            pq.push({i-j, i, j});
        }
    }
    sort(all(vec));
    ll ans = 0LL;
    while(D.cc != 1){
        auto [d, i, j] = pq.top(); pq.pop();
        if(v[j] == 1){
            if(i%j == d){
                if(!D.same(mp[i], mp[j])){
                    D.merge(mp[i], mp[j]);
                    ans += d;
                }
            }
        }
        else{
            for(int k=sz(w[j])-1; k>=0; k--){
                if(i%w[j][k] != d) break;
                if(!D.same(mp[i], mp[w[j][k]])){
                    D.merge(mp[i], mp[w[j][k]]);
                    ans += d;
                }
                if(D.cc == 1) break;
            }
        }
        if(v[j] == 2){
            j = p[j];
            pq.push({i-j, i, j});
        }
    }
    cout << ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 0 / 14
• Subtask 10: 14 / 14