제출 #1141210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141210		madamadam3	Sirni (COCI17_sirni)	C++17	0 / 140	374 ms	69784 KiB

sirni

#include <bits/stdc++.h>

using namespace std;

// typedefs
// #define int long long int
typedef long long ll;
typedef long double ld;
using str = string;
// typedef double ld;

// pairs
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

// vectors
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());}

// queues
template<class T> using prq = priority_queue<T, V<T>>;

// macros
#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";}

vi parent;

int fs(int v) {
    if (v == parent[v]) {
        return v;
    }
    return parent[v] = fs(parent[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 (n<->n has a cost of 0)
    set<int> ts(all(p)); // ts ??
    p.assign(all(ts));
    n = p.size();
    srt(p);

    // step 2: clever pruning
    // the idea is that the lower modulo is always the closest number to a multiple of that number
    // so we just store the next largest actual value for each value in the range [0, max(p)]
    // then iterate through all multiples of the number, adding possible edges as we do
    vi next_largest_node(largest + 1, -1); // for some multiple kn of n, whats the nearest actual value to it?
    FOR(i, 0, n) {next_largest_node[p[i]] = i;} // for each actual value, the closest actual value to it is itself
    ROF(i, largest, 0) {if (next_largest_node[i] == -1) {next_largest_node[i] = next_largest_node[i + 1];}} // work backwards

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

    vweg edges;
    FOR(i, 0, n - 1) {
        edges.pb(mp(p[i] % p[i + 1], mp(i, i + 1)));
        for (int curval = 2 * p[i]; curval <= largest; curval += p[i]) { // iterate through all multiples of the current toilent
            int next_node = next_largest_node[curval];                   //
            edges.pb(mp(p[next_node] % p[i], mp(next_node, i)));
        }
    }

    // step 4: mst
    srt(edges);
    int cost = 0;

    each(edge, edges) {
        int ec = edge.f;
        int u = edge.s.f;
        int v = edge.s.s;

        u = fs(u);
        v = fs(v);

        if (u != v) {
            parent[v] = u;
            cost += ec;
        }
    }

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

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

    solve();
}

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