Submission #485398

#	Time	Username	Problem	Language	Result	Execution time	Memory
485398		couplefire	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	611 ms	40848 KiB

railroad

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second

const int N = 400100;

int n, m, val[N], fa[N];
map<int, int> coords;
vector<int> good;
vector<pair<int, pair<int, int>>> edges;

int find(int v){return v==fa[v]?v:fa[v]=find(fa[v]);}

void unite(int u, int v){
    u = find(u), v = find(v);
    if(u==v) return;
    fa[u] = v;
}

ll plan_roller_coaster(vector<int> _s, vector<int> _t){
    _s.push_back(1e9);
    _t.push_back(1);
    n = _s.size();
    for(int i = 0; i<n; ++i)
        good.push_back(_s[i]), good.push_back(_t[i]);
    sort(good.begin(), good.end());
    good.erase(unique(good.begin(), good.end()), good.end());
    m = good.size();
    iota(fa, fa+N, 0);
    for(int i = 0; i<m; ++i)
        coords[good[i]] = i;
    for(int i = 0; i<n; ++i)
        ++val[coords[_s[i]]], --val[coords[_t[i]]], unite(coords[_s[i]], coords[_t[i]]);
    int curcnt = 0; ll ans = 0;
    for(int i = 0; i<m-1; ++i){
        curcnt += val[i];
        if(curcnt>0) ans += 1ll*curcnt*(good[i+1]-good[i]), unite(i, i+1);
        else if(curcnt<0) unite(i, i+1);
        val[i] -= curcnt, val[i+1] += curcnt;
        curcnt = 0;
    }
    for(int i = 0; i<m-1; ++i)
        edges.push_back({good[i+1]-good[i], {i, i+1}});
    sort(edges.begin(), edges.end());
    for(auto e : edges)
        if(find(e.s.f)!=find(e.s.s))
            ans += e.f, unite(e.s.f, e.s.s);
    return ans;
}

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