제출 #639645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
639645		piOOE	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	252 ms	18368 KiB

railroad

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

using namespace std;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    s.push_back(1e9 + 228);
    t.push_back(0);

    vector<int> x(s.begin(), s.end());
    x.insert(x.end(), t.begin(), t.end());
    sort(x.begin(), x.end());
    x.resize(unique(x.begin(), x.end()) - x.begin());

    const int n = s.size(), m = x.size();

    vector<int> b(m), p(m);

    iota(p.begin(), p.end(), 0);

    auto get = [&](int x) {
        while (x != p[x]) x = p[x] = p[p[x]];
        return x;
    };

    auto unite = [&](int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return false;
        p[b] = a;
        return true;
    };

    for (int i = 0; i < n; ++i) {
        int S = lower_bound(x.begin(), x.end(), s[i]) - x.begin();
        int T = lower_bound(x.begin(), x.end(), t[i]) - x.begin();
        ++b[S];
        --b[T];
        unite(S, T);
    }

    vector<array<int, 3>> edges;

    long long ans = 0;
    int balance = 0;
    for (int i = 0; i < m; ++i) {
        if (balance != 0) {
            ans += 1LL * (x[i] - x[i - 1]) * max(0, balance);
            unite(i, i - 1);
        }
        balance += b[i];
        if (i > 0) {
            edges.push_back({x[i] - x[i - 1], i, i - 1});
        }
    }

    sort(edges.begin(), edges.end());
    for (auto [w, u, v]: edges) {
        if (unite(u, v)) {
            ans += w;
        }
    }

    return ans;
}

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