Submission #370606

#	Time	Username	Problem	Language	Result	Execution time	Memory
370606		KoD	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	234 ms	15332 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"

template <class T>
using Vec = std::vector<T>;
using ll = long long;

constexpr int MAX = 1000000000;

struct DSU {
    Vec<int> par;
    DSU(const int n): par(n, -1) { }
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    bool merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            return false;
        }
        if (par[u] > par[v]) {
            std::swap(u, v);
        }
        par[u] += par[v];
        par[v] = u;
        return true;
    }
};

ll plan_roller_coaster(Vec<int> s, Vec<int> t) {
    s.push_back(MAX);
    t.push_back(1);
    const int n = (int) s.size();
    Vec<int> cmp;
    cmp.reserve(2 * n);
    std::copy(s.cbegin(), s.cend(), std::back_inserter(cmp));
    std::copy(t.cbegin(), t.cend(), std::back_inserter(cmp));
    std::sort(cmp.begin(), cmp.end());
    cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
    for (auto &x: s) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    for (auto &x: t) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    const int len = (int) cmp.size();
    Vec<int> coeff(len);
    for (const auto x: s) {
        coeff[x] -= 1;
    }
    for (const auto x: t) {
        coeff[x] += 1;
    }
    int current = 0;
    DSU dsu(len);
    ll ret = 0;
    Vec<std::tuple<int, int, int>> edges;
    for (int i = 0; i < len; ++i) {
        current += coeff[i];
        if (current < 0) {
            ret += (ll) -current * (cmp[i + 1] - cmp[i]);
        }
        if (current != 0) {
            dsu.merge(i, i + 1);
        }
        else if (i + 1 != len) {
            edges.emplace_back(cmp[i + 1] - cmp[i], i, i + 1);
        }
    }
    for (int i = 0; i < n; ++i) {
        dsu.merge(s[i], t[i]);
    }
    std::sort(edges.begin(), edges.end());
    for (const auto [c, u, v]: edges) {
        if (dsu.merge(u, v)) {
            ret += c;
        }
    }
    return ret;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36