Submission #274430

#	Time	Username	Problem	Language	Result	Execution time	Memory
274430		hamerin	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	431 ms	58976 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

void dfs(int here, const vector<vector<int>> &graph, vector<int> &palette,
         int color) {
    if (palette[here]) return;

    palette[here] = color;
    for (auto there : graph[here]) dfs(there, graph, palette, color);
}

class disjointSet {
   public:
    vector<int> p;

    disjointSet() = default;
    explicit disjointSet(int N) {
        p.clear();
        p.resize(N);
        for (int i = 0; i < N; i++) p[i] = i;
    }

    int find(int u) { return p[u] = (p[u] == u ? u : find(p[u])); }

    void mer(int u, int v) { p[find(v)] = find(u); }

    bool sset(int u, int v) { return find(u) == find(v); }
};


i64 plan_roller_coaster(vector<int> s, vector<int> t) {
    const int N = (int)s.size();

    vector<i64> X;
    copy(iterall(s), back_inserter(X));
    copy(iterall(t), back_inserter(X));
    sort(iterall(X));
    X.erase(unique(iterall(X)), X.end());

    const int M = (int)X.size();

    vector<i64> deg(M);
    vector<vector<int>> pregraph(M);
    for (int i = 0; i < N; i++) {
        auto S = lower_bound(iterall(X), s[i]) - X.begin();
        auto T = lower_bound(iterall(X), t[i]) - X.begin();

        pregraph[S].emplace_back(T);
        deg[S]++;
        deg[T]--;
    }

    i64 ret = 0;
    for (int i = 0; i < M - 1; i++) {
        i64 targetDeg = (i ? 0 : 1);
        i64 diff = targetDeg - deg[i];

        if (deg[i] < targetDeg) {
            pregraph[i].emplace_back(i + 1);
        } else if (deg[i] > targetDeg) {
            pregraph[i + 1].emplace_back(i);
            ret -= (diff * (X[i + 1] - X[i]));
        }

        deg[i] += diff;
        deg[i + 1] -= diff;
    }

    int color = 1;
    vector<int> palette(M);
    for (int i = 0; i < M; i++) {
        if (palette[i]) continue;
        dfs(i, pregraph, palette, color++);
    }

    priority_queue<tli, vector<tli>, greater<>> pq;
    for (int i = 0; i < M - 1; i++) {
        if (palette[i] == palette[i + 1]) continue;
        pq.emplace(X[i + 1] - X[i], palette[i], palette[i + 1]);
    }

    auto dS = disjointSet(color);
    while (!pq.empty()) {
        auto [w, u, v] = pq.top();
        pq.pop();

        if (!dS.sset(u, v)) dS.mer(u, v), ret += w;
    }

    return ret;
}

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