Submission #535438

#	Time	Username	Problem	Language	Result	Execution time	Memory
535438		mario05092929	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	451 ms	50616 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
const ll INF = 1e18;
int n,m;
vec s,t;
ll bitdp[1 << 16][16];
int ind[400005],oud[400005],mx;
int c[400005],p[400005];
vec rev;
vector <int> v[400005];
vector <pair<int,pi>> edge;

int Find(int x) {return (x == p[x] ? x : p[x] = Find(p[x]));}

ll dist(int x,int y) {
    return max(0,t[x]-s[y]);
}

void merge(int x,int y) {
    x = Find(x), y = Find(y);
    if(x == y) return;
    p[y] = x;
}

void dfs(int x,int co) {
    if(p[x] != -1) return;
    p[x] = co;
    for(int i : v[x]) dfs(i,co);
}

ll plan_roller_coaster(vec S,vec T) {
    s = S, t = T;
    n = s.size();
    for(int i = 0;i < n;i++) {
        rev.push_back(s[i]);
        rev.push_back(t[i]);
    }
    sort(rev.begin(),rev.end());
    rev.erase(unique(rev.begin(),rev.end()),rev.end());
    m = rev.size();
    for(int i = 0;i < n;i++) {
        s[i] = lower_bound(rev.begin(),rev.end(),s[i])-rev.begin();
        t[i] = lower_bound(rev.begin(),rev.end(),t[i])-rev.begin();
        oud[s[i]]++, ind[t[i]]++;
        v[s[i]].push_back(t[i]);
    }
    ll ans = 0;
    for(int i = 0;i < m-1;i++) {
        int tmp = ind[i]-oud[i];
        if(!i) tmp++;
        if(ind[i] > oud[i]+(i?0:-1)) v[i].push_back(i+1);
        if(ind[i] < oud[i]+(i?0:-1)) ans -= 1LL*(rev[i+1]-rev[i])*tmp, v[i+1].push_back(i);
        oud[i] += tmp;
        ind[i+1] += tmp;
        edge.push_back({rev[i+1]-rev[i],{i,i+1}});
    }
    sort(edge.begin(),edge.end());
    memset(p,-1,sizeof(p));
    for(int i = 0;i < m;i++) dfs(i,i);
    for(auto i : edge) {
        int x = i.y.x, y = i.y.y;
        int cost = i.x;
        if(Find(x) == Find(y)) continue;
        //cout << x << ' ' << y << " : " << cost << '\n';
        merge(x,y);
        ans += cost;
    }

    return ans;
}

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