Submission #972955

#	Time	Username	Problem	Language	Result	Execution time	Memory
972955		TahirAliyev	Sirni (COCI17_sirni)	C++17	140 / 140	1691 ms	575712 KiB

sirni

#include <bits/stdc++.h>
 
using namespace std;
 
#define oo 1e9
#define pii pair<int, int>
#define ll long long
#define all(v) v.rbegin(), v.rend()
 
int n, k, m;
const int MAX = 1e5 + 5, MOD = 998244353;
 
int arr[MAX];
 
struct DSU{
    int par[MAX];
    void init(){
        for(int i = 1; i <= n; i++) par[i] = -1;
    } 
    int get(int node){
        if(par[node] < 0) return node;
        return get(par[node]);
    }
    bool unite(int u, int v){
        u = get(u), v = get(v);
        if(u == v) return 0;
        if(-par[u] < -par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return 1;
    }
};
 
DSU dsu;
int nxt[int(1e7 + 7)];
vector<pii> E[int(1e7 + 7)];
 
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    sort(arr + 1, arr + n + 1);
    dsu.init();
    int pos = 1;
    for(int i = 1; i <= 1e7; i++){
        while(arr[pos] < i){
            pos++;
            if(pos == n + 1) break;
        }
        if(pos == n + 1) break;
        nxt[i] = pos;
    }
    for(int i = 1; i <= n; i++){
        if(arr[i] == arr[i - 1]) continue;
        for(int j = arr[i]; j <= 1e7; j += arr[i]){
            int nx = nxt[j + (j == arr[i])];
            if(nx && arr[nx] < j + arr[i]){
                E[arr[nx] - j].push_back({i, nx});
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i <= 1e7; i++){
        for(auto a : E[i]){
            if(dsu.unite(a.first, a.second)) ans += i;
        }
    }   
    cout << ans << '\n';
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--) solve();
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 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: 14 / 14
• Subtask 10: 14 / 14