Submission #1289146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289146		imann	Sirni (COCI17_sirni)	C++20	140 / 140	883 ms	379036 KiB

sirni

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>

using ll = long long;

const int MAX_N = 100*1000 + 2;
const int MAX_P = 10*1000*1000 + 2;

std::array<std::pair<int, int>, MAX_P> closestP;
std::array<std::vector<std::pair<int, int>>, MAX_P> bucketEdges;

struct Edge {
    int s, e, w;
};

class Dsu {
private:
    std::vector<int> sizes, parents;
public:
    Dsu(int n) {
        sizes.resize(n);
        parents.resize(n);
        for (int i = 0; i < n; ++i) {
            sizes[i] = 1;
            parents[i] = i;
        } 
    }

    int find(int x) {
        int px = parents[x];
        if (x == px)
            return x;
        int ppx = find(px);
        parents[x] = ppx;
        return ppx;
    }

    bool unite(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px == py)
            return false;
        if (sizes[px] < sizes[py]) {
            std::swap(px, py);
        }
        parents[py] = px;
        sizes[px] += sizes[py];
        return true;
    }
};

int solve(const std::vector<int> &Ps) {
    closestP.fill({-1, -1});
    for (int i = Ps.size() - 1; i >= 0; --i) {
        int prevP = 0;
        if (i > 0) {
            prevP = Ps[i - 1];
        }
        for (int j = Ps[i]; j > prevP; --j) {
            closestP[j] = {Ps[i], i};
        }
    }
    for (int i = 0; i < Ps.size(); ++i) {
        int mult = Ps[i];
        while (mult < MAX_P) {
            int nextMult = mult + Ps[i];
            if (closestP[mult].first != -1 && closestP[mult].first < nextMult) {
                bucketEdges[closestP[mult].first - mult].push_back({i, closestP[mult].second});
            }
            mult = nextMult;
        }
    }
    for (int i = 0; i < Ps.size(); ++i) {
        if (i > 0) {
            bucketEdges[Ps[i] - Ps[i - 1]].push_back({i, i - 1});
        }
    }
    Dsu dsu(Ps.size());
    int edgeCount = 0;
    ll ans = 0;
    for (int b = 0; b < MAX_P; ++b) {
        bool flag = false;
        for (auto edge : bucketEdges[b]) {
            if (dsu.unite(edge.first, edge.second)) {
                ans += b;
                edgeCount++;
                if (edgeCount == Ps.size() - 1) {
                    flag = true;
                    break;
                }
            }
        }
        if (flag)
            break;
    }
    return ans;
}

int main() {
    int n; std::cin >> n;
    std::vector<int> Ps, TempPs;
    for (int i = 0; i < n; ++i) {
        int a; std::cin >> a;
        TempPs.push_back(a);
    }
    std::sort(TempPs.begin(), TempPs.end());
    int lastP = -1;
    for (auto p : TempPs) {
        if (p != lastP) {
            lastP = p;
            Ps.push_back(p);
        }
    }
    std::cout << solve(Ps) << std::endl;
}

• 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