Submission #559171

#	Time	Username	Problem	Language	Result	Execution time	Memory
559171		elazarkoren	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	241 ms	21936 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int infinity = 2e9;
const int MAX_N = 2e5 + 5;

vi vals;
inline int Val(int x) {
    return lower_bound(all(vals), x) - vals.begin();
}

int add[2 * MAX_N];

struct Dsu {
    vi par, sz;
    Dsu() {}
    Dsu(int n) {
        par.resize(n), sz.resize(n, 1);
        iota(all(par), 0);
    }
    int Find(int i) {
        return par[i] == i ? i : par[i] = Find(par[i]);
    }
    bool Union(int a, int b) {
        int pa = Find(a), pb = Find(b);
        if (pa == pb) return false;
        if (sz[pa] < sz[pb]) swap(pa, pb);
        par[pb] = pa;
        sz[pa] += sz[pb];
        return true;
    }
};

ll plan_roller_coaster(vi s, vi t) {
    int n = s.size();
    s.push_back(infinity), t.push_back(0);
    for (int i = 0; i <= n; i++) vals.push_back(s[i]), vals.push_back(t[i]);
    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    for (int &x : s) {
        x = Val(x);
        add[x]++;
    }
    for (int &x : t) {
        x = Val(x);
        add[x]--;
    }
    int sz = vals.size();
    Dsu dsu(sz);
    for (int i = 0; i <= n; i++) dsu.Union(s[i], t[i]);
    ll ans = 0;
    for (int i = 0, balance = 0; i < sz; i++) {
        balance += add[i];
        if (balance > 0) ans += ll(balance) * (vals[i + 1] - vals[i]);
        if (balance) dsu.Union(i, i + 1);
    }
    vector<pair<ll, pii>> edges;
    for (int i = 0; i < sz - 1; i++) {
        edges.push_back({vals[i + 1] - vals[i], {i, i + 1}});
    }
    sort(all(edges));
    for (auto [x, p] : edges) {
        ans += x * dsu.Union(p.x, p.y);
    }
    return ans;
}

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