Submission #1191476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191476		TheSahib	Sirni (COCI17_sirni)	C++17	14 / 140	299 ms	326224 KiB

sirni

#include <bits/stdc++.h>


using namespace std;
 
#define ll long long
#define all(v) v.begin(), v.end()
#define pii pair<int, int>

const int MAX = 1e7 + 100, MOD = 1e9 + 7, oo = 1e18;


int par[MAX],sz[MAX];
int get(int a){
    if(par[a]==-1)return a;
    return par[a]=get(par[a]);
}
bool unite(int a,int b){
    a=get(a);
    b=get(b);
    if(a==b)return false;
    if(sz[a]>sz[b])swap(a,b);
    sz[b]+=sz[a];
    par[a]=b;
    return true;
}

vector<array<int, 2>> edges[MAX];
int lb[MAX];

void solve(){
    memset(par, -1, sizeof(par));
    int n; cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        sz[i] = 1;
    }
    
    sort(all(v));
    v.erase(unique(all(v)), v.end());

    lb[v[n - 1]] = n - 1;
    for(int i = v[n - 1] - 1; i >= 0; --i){
        if(lb[i + 1] == 0){
            lb[i] = 0;
            continue;
        }
        if(v[lb[i + 1] - 1] >= i) lb[i] = lb[i + 1] - 1;
        else lb[i] = lb[i + 1];
    }

    for (int i = 0; i < v.size() - 1; i++)
    {
        int x = v[i];
        edges[v[i + 1] % v[i]].push_back({i, i + 1});
        for(int l = x * 2; l <= v[n - 1]; ){
            int j = lb[l];
            edges[v[j] % v[i]].push_back({i, j});
            l = (v[j] / x + 1) * x;
        }
    }
    long long ans = 0;
    for(int c = 0; c < MAX; ++c){
        for(auto& e:edges[c]){
            if(unite(e[0], e[1])){
                ans += c;
            }
        }
    }
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

sirni.cpp:10:48: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   10 | const int MAX = 1e7 + 100, MOD = 1e9 + 7, oo = 1e18;
      |                                                ^~~~

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