Submission #1121473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121473		nhatminhgpt2008	Sirni (COCI17_sirni)	C++17	140 / 140	2675 ms	537068 KiB

sirni

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
const int M = 1e7+5;

int n;
vector<int> a;
vector<pair<int,int>> edges[M];
int par[N], nodes[N];

int acs(int u) {
    return (par[u] == 0 ? par[u] = u : (par[u] == u ? u : par[u] = acs(par[u])));
}

bool combine(int u, int v) {
    u = acs(u); if (!nodes[u]) nodes[u] = 1;
    v = acs(v); if (!nodes[v]) nodes[v] = 1;
    if (u == v) return false;
    if (nodes[u] < nodes[v]) swap(u,v);
    par[v] = u;
    nodes[u] += nodes[v];
    return true;
}

void compress() {
    a.push_back(-1);
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    n = a.size() - 1;
}

main() {
    #define TASK "TASK"
//    freopen("TASK.inp","r",stdin);
//    freopen("TASK.out","w",stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    compress();
    for (int i = 2; i <= n; i++) {
        edges[a[i] % a[i-1]].push_back({i, i-1});
    }
    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j <= 1e7;) {
            int l = i+1, r = n, p = -1;
            while (l <= r) {
                int m = (l+r) >> 1;
                if (a[m] >= j) {
                    p = m;
                    r = m - 1;
                }
                else {
                    l = m + 1;
                }
            }
            if (p == -1) {
                break;
            }
            edges[a[p] % a[i]].push_back({p, i});
            j = a[p] / a[i] * a[i] + a[i];
        }
    }
    long long ans = 0;
    for (int i = 0; i < M; i++) {
        for (auto e : edges[i]) {
            int u = e.first;
            int v = e.second;
            if (combine(u,v)) {
                ans += i;
            }
        }
    }
    cout << ans;
}

Compilation message (stderr)

sirni.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main() {
      | ^~~~

• 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