Submission #1317206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317206		anarch_y	Sirni (COCI17_sirni)	C++20	84 / 140	4726 ms	851968 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;
    for(int i=1; i<=m; i++){
        if(v[i] == 1){
            int j = p[i];
            if(j == 0) continue;
            while(true){
                vec.pb({i-j, i, j});
                if(v[j] == 1) break;
                j = p[j];
            }
        }
    }
    sort(all(vec));
    ll ans = 0LL;
    for(auto [d, i, j]: vec){
        if(D.cc == 1) break;
        for(auto k: w[j]){
            if(i%k == d){
                if(!D.same(mp[i], mp[k])){
                    D.merge(mp[i], mp[k]);
                    ans += d;
                }
            }
            if(D.cc == 1) break;
        }
    }
    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: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14