Submission #434408

#	Time	Username	Problem	Language	Result	Execution time	Memory
434408		79brue	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	877 ms	88636 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"

using namespace std;

typedef long long ll;

struct Edge{
    int x, y; ll z;
    Edge(){}
    Edge(int x, int y, ll z): x(x), y(y), z(z){}

    bool operator<(const Edge &r)const{
        return z > r.z;
    }
};

int n, k;
vector<int> vec;
map<int, int> idx;

vector<int> link[500002];
vector<int> revLink[500002];

ll ans;

int par[500002];

int find(int x){
    if(x == par[x]) return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y){
    x = find(x), y = find(y);
    par[x] = y;
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    n = (int)s.size();
    for(int i=0; i<n; i++){
        vec.push_back(s[i]);
        vec.push_back(t[i]);
    }

    vec.push_back(1);
    vec.push_back(1e9);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    k = (int)vec.size();
    for(int i=0; i<k; i++) idx[vec[i]] = i;

    for(int i=0; i<n; i++){
        s[i] = idx[s[i]];
        t[i] = idx[t[i]];
        link[s[i]].push_back(t[i]);
        revLink[t[i]].push_back(s[i]);
    }
    link[k-1].push_back(0);
    revLink[0].push_back(k-1);

    int need = 0;
    for(int i=0; i<k; i++){
        need += (int)link[i].size();
        need -= (int)revLink[i].size();

        if(need < 0){
            link[i].push_back(i+1);
            revLink[i+1].push_back(i);
            need++;
        }
        else if(need > 0){
            link[i+1].push_back(i);
            revLink[i].push_back(i+1);
            ans += ll(vec[i+1] - vec[i]) * need;
            need--;
        }
    }

    for(int i=0; i<k; i++) par[i] = i;
    for(int i=0; i<k; i++){
        for(auto x: link[i]){
            merge(i, x);
        }
    }

    priority_queue<Edge> pq;
    for(int i=0; i<k-1; i++){
        pq.push(Edge(i, i+1, vec[i+1] - vec[i]));
    }

    while(!pq.empty()){
        Edge tmp = pq.top(); pq.pop();
        if(find(tmp.x) == find(tmp.y)) continue;
        ans += tmp.z;
        merge(tmp.x, tmp.y);
    }

    return ans;
}

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