Submission #617446

#	Time	Username	Problem	Language	Result	Execution time	Memory
617446		MetalPower	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	145 ms	17940 KiB

railroad

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

#include "railroad.h"

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e5 + 10;

int N;
vector<pair<int, pii>> vec;

struct dsu{
    int p[MX];

    void init(){
        for(int i = 0; i < MX; i++) p[i] = i;
    }

    int f(int x){
        if(x == p[x]) return x;
        else return p[x] = f(p[x]);
    }

    bool Join(int u, int v){
        int fu = f(u), fv = f(v);
        if(fu == fv) return false;
        p[fu] = fv;
        return true;
    }
} D;

long long plan_roller_coaster(vector<int> s, vector<int> t) {

    D.init();
    N = s.size();

    for(int i = 0; i < N; i++){
        vec.push_back({s[i], {i, 1}});
        vec.push_back({t[i], {i, -1}});
    }
    vec.push_back({1000000000, {N + 1, 1}});
    vec.push_back({1, {N + 1, -1}});


    sort(vec.begin(), vec.end());

    // Let the values be on a line 
    // We will calculate how many times a distance is traversed

    // A distance is traversed optimally X times if there are X S values below this that do not have a T pair
    // However because we cannot pair ith S with the ith T
    // The T will be forced to pair with an S lower than this

    int numS = 0; ll ans = 0;
    int sz = vec.size();

    vector<pair<int, pii>> E;

    for(int i = 0; i < sz - 1; i++){

        if(vec[i].se.se == 1) numS++;
        else numS--;

        if(numS > 0) ans += 1ll * numS * (vec[i + 1].fi - vec[i].fi);
        if(numS != 0){
            D.Join(vec[i].se.fi, vec[i + 1].se.fi);
        }else{
            E.push_back({vec[i + 1].fi - vec[i].fi, {vec[i].se.fi, vec[i + 1].se.fi}});
        }
    }

    // Force to pair with someone lower

    sort(E.begin(), E.end());

    numS = 0;
    for(auto x : E){
        if(D.f(x.se.se) != D.f(x.se.fi)){
            D.Join(x.se.se, x.se.fi);
            ans += x.fi;
        }
    }
    
    return ans;
}

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