Submission #253107

#	Time	Username	Problem	Language	Result	Execution time	Memory
253107		Hehehe	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	297 ms	35456 KiB

railroad

#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "railroad.h"

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int H = 2e6 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

ll n, m, p[H], siz[H];
ll pref[H];

struct edge{
    ll ff, ss, w;
};

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

void unionn(int x, int y){

    x = find_set(x);
    y = find_set(y);

    if(x == y)return;

    if(siz[x] < siz[y])swap(x, y);

    p[y] = x;
    siz[x] += siz[y];
}

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

    n = (ll)sz(s);
    ll ans = 0;

    vector<ll>v;

    for(int i = 0; i < n; i++){
        v.push_back(s[i]);
        v.push_back(t[i]);
    }

    sort(all(v));
    v.resize(unique(all(v))-v.begin());

    m = sz(v);

    for(int i = 0; i <= m; i++){
        p[i] = i;
        pref[i] = 0;
        siz[i] = 1;
    }

    pref[0] = -1;
    for(int i = 0; i < n; i++){
        s[i] = lower_bound(all(v), s[i]) - v.begin();
        t[i] = lower_bound(all(v), t[i]) - v.begin();

        pref[s[i]]++;
        pref[t[i]]--;

        unionn(s[i], t[i]);
    }

    vector<edge>edges;

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

        pref[i] += (i == 0 ? 0 : pref[i - 1]);

        if(pref[i] != 0){
            ans += max(0ll, pref[i])*(v[i + 1] - v[i]);
            unionn(i, i + 1);
        }

        edges.push_back({i, i + 1, v[i + 1] - v[i]});
    }

    sort(all(edges), [](edge l, edge r){
         return (l.w < r.w);
    });

    for(auto it : edges){
        if(find_set(it.ff) == find_set(it.ss))continue;

        ans += it.w;
        unionn(it.ff, it.ss);
    }

    return ans;
}

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