Submission #162604

#	Time	Username	Problem	Language	Result	Execution time	Memory
162604		rama_pang	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	383 ms	24516 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e9;

lint plan_roller_coaster(vector<int> s, vector<int> t) {
    s.emplace_back(INF), t.emplace_back(1);
    int N = s.size(), M;
    vector<int> coord, flow;
    vector<tuple<int, int, int>> edges; // tuple < cost, endpoint 1, endpoint 2 >
    lint res = 0;
    
    /* Coordinate compressions */
    auto get_pos = [&] (int n) { 
        return lower_bound(coord.begin(), coord.end(), n) - coord.begin();
    };

    for (int i = 0; i < N; i++)
        coord.emplace_back(s[i]), coord.emplace_back(t[i]);
    
    sort(coord.begin(), coord.end());
    coord.resize(unique(coord.begin(), coord.end()) - coord.begin());

    M = coord.size(), flow.resize(M);

    for (int i = 0; i < N; i++) {
        s[i] = get_pos(s[i]), t[i] = get_pos(t[i]);
        flow[s[i]]++, flow[t[i]]--; // if s[i] < t[i], [s[i], t[i]) + 1, else [s[i], t[i]) - 1
        edges.emplace_back(0, s[i], t[i]);
    }
    
    for (int i = 1; i < M; i++)
        flow[i] += flow[i - 1];

    for (int i = 0; i < M - 1; i++) {
        res += max(0ll, (lint)flow[i] * (coord[i + 1] - coord[i]));
        if (flow[i] == 0)
            edges.emplace_back(coord[i + 1] - coord[i], i, i + 1);
        else
            edges.emplace_back(0, i, i + 1);
    }

    /* Disjoint Set Union Find Data Structure */
    vector<int> par(M);
    iota(par.begin(), par.end(), 0);
    auto find = [&](int n) {
        auto lambda = [&](int n, const auto &lambda) {
            if (par[n] == n) return n;
            return par[n] = lambda(par[n], lambda);
        };
        return lambda(n, lambda);
    };

    /* Minimum Spanning Tree */
    sort(edges.begin(), edges.end());
    for (auto e : edges) {
        if (find(get<1>(e)) != find(get<2>(e))) {
            res += get<0>(e);
            par[find(get<1>(e))] = find(get<2>(e));
        }
    }

    return res;
}

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