Submission #1131310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131310		narzarech	Sirni (COCI17_sirni)	C++20	42 / 140	5123 ms	668592 KiB

sirni

#include <fstream>
#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long

int find(vector<int>& root, int x) {
    return (x == root[x]) ? x : (root[x] = find(root, root[x]));
}

bool unite(vector<int>& root, vector<int> size, int a, int b) {
    int rA = find(root, a), rB = find(root, b);
    if (rA == rB) return false;
    if (size[rA] > size[rB]) swap(rA, rB);
    size[rB] += size[rA];
    root[rA] = rB;
    return true;
}

ll solve(vector<int>& p, int n) {
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    n = p.size();

    int largest = p.back();
    vector<int>next(largest + 1, -1);
    for (int i = 0; i < n; ++i) next[p[i]] = i;
    for (int i = largest; i >= 0; --i)
        next[i] = (next[i] != -1) ? next[i] : next[i + 1];

    // w - [(u, v)]
    vector<vector<pair<int, int>>>candidates(largest + 1);
    for (int i = 0; i < n - 1; ++i) {
        // Cover from range [p_i, 2 * p_i)
        candidates[p[i + 1] % p[i]].push_back({i, i + 1});
        // Cover from range [2 * p_i, largest]
        for (int k = 2; k * p[i] <= largest; ++k) {
            int v = next[k * p[i]], w = p[v] % p[i];
            candidates[w].push_back({i, v});
        }
    }

    int cnt = 0;
    ll res = 0;
    vector<int>root(n), size(n, 1); for (int i = 0; i < n; ++i) root[i] = i;
    for (int i = 0; i < candidates.size(); ++i) {
        for (int j = 0; j < candidates[i].size(); ++j) {
            int u, v; tie(u, v) = candidates[i][j];
            if (unite(root, size, u, v)) {
                ++cnt;
                res += i;
                if (cnt == n - 1) return res;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    vector<int>p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    cout << solve(p, n);

    return 0;
}

Compilation message (stderr)

sirni.cpp: In function 'long long int solve(std::vector<int>&, int)':
sirni.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^

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