Submission #1122328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122328		dosts	Sirni (COCI17_sirni)	C++17	0 / 140	2452 ms	786432 KiB

sirni

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
int MOD = 1e9+7,inf = 2e18;
const int N = 1e5+50,Q = 2e5+50;


struct DSU {
    vi dad,sz;

    DSU(int nn) {
        dad.resize(nn+1);
        iota(all(dad),0ll);
        sz.assign(nn+1,1);
    }

    int find(int x) {
        if (x == dad[x]) return x;
        return dad[x] = find(dad[x]);
    }

    void unite(int x,int y) {
        int a = find(x),b = find(y);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a,b);
        dad[b] = a;
        sz[a]+=sz[b];
    }
};

vi have[10000001];
int orig[10000001];

struct Edge {
    int u,v,w;
};
void solve() {
    int n;
    cin >> n;
    vi p(n);
    for (int i=0;i<n;i++) cin >> p[i];
    sort(p.begin(),p.end());
    vi pp;
    for (int i = 0;i<n;i++) if (!i || p[i] != p[i-1]) pp.push_back(p[i]);
    n = pp.size();
    for (int i = 0;i<n;i++) {
        orig[pp[i]] = i+1;
        for (int j = pp[i];j<=10000000;j+=pp[i]) have[j].push_back(i+1);
    }
    vector<pii> collect;
    vector<Edge> edges;
    long long ans = 0;
    for (int i = 1;i<=10000000;i++) {
        for (auto it : have[i]) collect.push_back({it,i});
        if (orig[i]) {
            for (auto it : collect) {
                if (it.ff != orig[i]) {
                    edges.push_back(Edge{it.ff,orig[i],i-it.ss});
                }
            }
            collect.clear();
        }
    }

    sort(all(edges),[&](const Edge& e1,const Edge& e2) {
        return e1.w < e2.w;
    });
    DSU dsu(n);
    for (auto it : edges) {
        if (dsu.find(it.u) != dsu.find(it.v)) {
            dsu.unite(it.u,it.v);
            ans+=it.w;
        }
    }
    cout << ans << '\n';
}                    
                             
int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message (stderr)

sirni.cpp:12:23: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   12 | int MOD = 1e9+7,inf = 2e18;
      |                       ^~~~

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