제출 #66311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66311		aquablitz11	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	302 ms	24732 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int N = 400010;
const int INF = 1e9+1;

int c;
vector<int> coord;
inline int pos(int x) { return upper_bound(coord.begin(), coord.end(), x) - coord.begin(); }
inline int &get(int i) { return coord[i-1]; }
int qs[N], par[N];

int root(int u) {
    if (!par[u]) return u;
    return par[u] = root(par[u]);
}

inline bool merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) return false;
    par[u] = v;
    return true;
}

long long plan_roller_coaster(vector<int> s, vector<int> t)
{
    // graph construction
    int n = s.size();
    coord.insert(coord.end(), s.begin(), s.end());
    coord.insert(coord.end(), t.begin(), t.end());
    coord.push_back(0);
    coord.push_back(INF);
    sort(coord.begin(), coord.end());
    coord.resize(unique(coord.begin(), coord.end())-coord.begin());
    c = coord.size();
    qs[pos(0)] -= 1;
    qs[pos(INF)] += 1;
    for (int i = 0; i < n; ++i) {
        int a = s[i], b = t[i], v = 1;
        if (a > b) swap(a, b), v = -1;
        a = pos(a), b = pos(b);
        merge(a, b);
        qs[a] += v;
        qs[b] -= v;
    }

    // cost calculation and dsu
    ll cost = 0;
    vector<pii> E;
    for (int i = 1; i <= c-1; ++i) {
        qs[i] += qs[i-1];
        ll dist = get(i+1)-get(i);
        cost += max(qs[i]*dist, 0ll);
        if (qs[i] != 0)
            merge(i, i+1);
        else
            E.push_back(pii(dist, i));
    }
    sort(E.begin(), E.end());
    for (auto e : E) {
        if (merge(e.second, e.second+1))
            cost += e.first;
    }

    return cost;
}

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