Submission #617414

#	Time	Username	Problem	Language	Result	Execution time	Memory
617414		MetalPower	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	111 ms	13492 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) {

    N = s.size();

    for(int i = 0; i < N; i++){
        vec.push_back({s[i], {i, 1}});
        vec.push_back({t[i], {i, -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();

    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);
    }

    // Force to pair with someone lower

    numS = 0;
    for(int i = 0; i < sz - 1; i++){
        if(D.f(vec[i].se.fi) != D.f(vec[i + 1].se.fi)){
            D.Join(vec[i].se.fi, vec[i + 1].se.fi);
            ans += vec[i + 1].fi - vec[i].fi;
        }
    }
    
    return ans;
}

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