Submission #1141212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141212		madamadam3	Sirni (COCI17_sirni)	C++17	84 / 140	5119 ms	833676 KiB

sirni

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

// Typedefs and macros (as in your original code)

typedef long long ll;
typedef long double ld;
using str = string;
template <class T> using P = pair<T, T>;
using pi = P<int>;
using pl = P<ll>;
using pd = P<ld>;
using weg = pair<int, pi>; // weighted edge

#define mp make_pair
#define f first
#define s second

template <class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;
using vd = V<ld>;
using vb = V<bool>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;
using vvi = V<vi>;
using vweg = V<weg>;

#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
#define pb push_back

#define lb lower_bound
#define ub upper_bound
template<class T> int ilb(V<T>& a, const T& b) {return int(lb(all(a), b) - (a).begin());}
template<class T> int iub(V<T>& a, const T& b) {return int(ub(all(a), b) - (a).begin());}

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (a); i >= (b); --i)
#define rep(a) FOR (_, 0, a) 
#define each(a, x) for (auto& a: x)
#define trace(x) each(a, (x)) {cout << a << " ";}
#define tracel(x) each(a, (x)) {cout << a << "\n";}

// DSU variables and functions
vi parent;
vi size_ds;

int fs(int v) {
    if (v == parent[v]) {
        return v;
    }
    return parent[v] = fs(parent[v]);
}

void unite_sets(int u, int v) {
    u = fs(u);
    v = fs(v);
    if (u != v) {
        if (size_ds[u] < size_ds[v]) swap(u, v);
        parent[v] = u;
        size_ds[u] += size_ds[v];
    }
}

void solve() {
    int n;
    cin >> n;

    int largest = -1; // the largest value of a node 
    vi p(n); 
    FOR(i, 0, n) {
        cin >> p[i];
        largest = max(largest, p[i]);
    }

    // Step 1: remove duplicates and sort
    set<int> ts(all(p));
    p.assign(all(ts));
    n = p.size();
    srt(p);

    // Step 2: clever pruning
    vi next_largest_node(largest + 1, -1);
    FOR(i, 0, n) { 
        next_largest_node[p[i]] = i; 
    }
    ROF(i, largest - 1, 0) { 
        if (next_largest_node[i] == -1) { 
            next_largest_node[i] = next_largest_node[i + 1];
        }
    }

    // Step 3: make edges 
    parent.resize(n);
    size_ds.resize(n, 1);
    iota(all(parent), 0);

    vweg edges;

    // Add edges between consecutive cards
    FOR(i, 0, n - 1) {
        edges.pb(mp(p[i + 1] % p[i], mp(i + 1, i)));
    }

    // Add edges based on multiples
    FOR(i, 0, n) {
        for (int curval = 2 * p[i]; curval <= largest; curval += p[i]) {
            int next_node = next_largest_node[curval];
            if (next_node != -1) { // Ensure valid index
                edges.pb(mp(p[next_node] % p[i], mp(next_node, i)));
            }
        }
    }

    // Step 4: sort edges by cost
    srt(edges);

    // Step 5: Kruskal's algorithm to find MST
    ll cost = 0;

    for(auto &edge : edges) {
        int ec = edge.f;
        int u = edge.s.f;
        int v = edge.s.s;

        int set_u = fs(u);
        int set_v = fs(v);

        if (set_u != set_v) {
            unite_sets(u, v);
            cost += (ll) ec;
        }
    }

    cout << cost << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14