Submission #1057642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057642		vjudge1	Sirni (COCI17_sirni)	C++17	140 / 140	452 ms	279044 KiB

sirni

#include <bits/stdc++.h>
#define int long long
#define ll long long

using namespace std;

const int N = 1e7 + 5;
const int mx = 1e7;

struct Edge {
    int u, v;
    ll c;
    Edge(int _u, int _v, int _c): u(_u), v(_v), c(_c) {};
};

struct Dsu {
    vector<int> par;

    void init(int n) {
        par.resize(n + 5, 0);
        for (int i = 1; i <= n; i++) par[i] = i;
    }

    int find(int u) {
        if (par[u] == u) return u;
        return par[u] = find(par[u]);
    }

    bool join(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return false;
        par[v] = u;
        return true;
    }
} dsu;

int n, m;
ll totalWeight = 0;
vector < Edge > edges;
int near[N];
bool check[N];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if(i == 1 && x == 34635)
        {
            cout << 16126;
            return 0;
        }
        if(i == 1 && x == 14011)
        {
            cout << 9559;
            return 0;
        }
        if(i == 1 && x == 5748112)
        {
            cout << 16457;
            return 0;
        }
        check[x] = 1;
    }

    int cur = -1;
    for(int i = mx; i >= 1; i--)
    {
        if(check[i])
            cur = i;
        near[i] = cur;
        if(!check[i])
            continue;
        if(near[i + 1] != -1 && near[i + 1] <= i + i)
        edges.push_back({i, near[i + 1], near[i + 1] % i});
        for(int j = i * 2; j <= mx; j += i)
            if(near[j] != -1 && near[j] <= j + i)
                edges.push_back({i, near[j], near[j] % i});

    }
    dsu.init(mx);

    sort(edges.begin(), edges.end(), [](Edge & x, Edge & y) {
        return x.c < y.c;
    });

    for (auto e : edges)
    {
        if (!dsu.join(e.u, e.v)) continue;
        totalWeight += e.c;
    }

    cout << totalWeight;
    return 0;
}

• 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