Submission #292558

#	Time	Username	Problem	Language	Result	Execution time	Memory
292558		Saboon	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	248 ms	20948 KiB

railroad

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

const int maxn = 2e5 + 10;
const int inf = 1e9;

int n;
int par[2*maxn];
ll degIn[2*maxn], degOut[2*maxn];

int get_par(int v){
    return par[v] < 0 ? v : par[v] = get_par(par[v]);
}

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

ll plan_roller_coaster(vector<int> s, vector<int> t){
    s.push_back(inf);
    t.push_back(1);
    n = s.size();
    vector<int> Cmp;
    for (auto it : s) Cmp.push_back(it);
    for (auto it : t) Cmp.push_back(it);
    sort(Cmp.begin(), Cmp.end());
    Cmp.resize(unique(Cmp.begin(), Cmp.end())-Cmp.begin());
    memset(par, -1, sizeof par);
    for (int i = 0; i < n; i++){
        s[i] = lower_bound(Cmp.begin(), Cmp.end(), s[i]) - Cmp.begin();
        t[i] = lower_bound(Cmp.begin(), Cmp.end(), t[i]) - Cmp.begin();
        merge(t[i],s[i]);
        degOut[s[i]] ++, degIn[t[i]] ++;
    }
    int m = Cmp.size();
    ll untilNow = 0;
    for (int i = 0; i < m-1; i++){
        if (degIn[i] == degOut[i])
            continue;
        ll diff = abs(degIn[i]-degOut[i]);
        merge(i,i+1);
        if (degIn[i] < degOut[i]){
            degIn[i] += diff;
            degOut[i+1] += diff;
            untilNow += 1LL*diff*(Cmp[i+1]-Cmp[i]);
        }
        else{
            degOut[i] += diff;
            degIn[i+1] += diff;
        }
    }
    vector<pair<ll,pair<int,int>>> E;
    for (int i = 0; i < m-1; i++)
        if (get_par(i) != get_par(i+1))
            E.push_back({Cmp[i+1]-Cmp[i],{get_par(i),get_par(i+1)}});
    sort(E.begin(),E.end());
    for (auto it : E){
        int v = it.second.first, u = it.second.second;
        if (merge(v,u))
            untilNow += it.first;
    }
    return untilNow;
}

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