Submission #163322

#	Time	Username	Problem	Language	Result	Execution time	Memory
163322		dolphingarlic	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	309 ms	19948 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
typedef long long ll;

int balance[404040], din[404040], dout[404040];
vector<pair<int, pair<int, int>>> edges;

int cmp[404040];
int find(int a) {
    while (cmp[a] != a) cmp[a] = cmp[cmp[a]], a = cmp[a];
    return a;
}
void onion(int a, int b) { cmp[find(a)] = cmp[find(b)]; }

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = s.size();

    FOR(i, 0, n) {
        balance[i * 2] = s[i];
        balance[i * 2 + 1] = t[i];
    }
    balance[2 * n] = 1;
    balance[2 * n + 1] = 2e9;

    sort(balance, balance + 2 * n + 2);
    FOR(i, 0, 2 * n + 2) cmp[i] = i;

    FOR(i, 0, n) {
        s[i] = lower_bound(balance, balance + 2 * n + 2, s[i]) - balance;
        t[i] = lower_bound(balance, balance + 2 * n + 2, t[i]) - balance;

        din[t[i]]++;
        dout[s[i]]++;
        onion(t[i], s[i]);
    }
    din[0]++;
    dout[2 * n + 1]++;
    onion(0, 2 * n + 1);

    ll ans = 0, sm = 0;
    FOR(i, 0, 2 * n + 1) {
        sm += dout[i] - din[i];
        if (sm < 0)
            onion(i, i + 1);
        else if (sm == 0)
            edges.push_back({balance[i + 1] - balance[i], {i, i + 1}});
        else {
            ans += sm * (balance[i + 1] - balance[i]);
            onion(i, i + 1);
        }
    }

    sort(edges.begin(), edges.end());
    for (auto& i : edges) {
        if (find(i.second.first) != find(i.second.second)) {
            onion(i.second.first, i.second.second);
            ans += i.first;
        }
    }

    return ans;
}

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