Submission #595278

#	Time	Username	Problem	Language	Result	Execution time	Memory
595278		Lucpp	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	942 ms	74732 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> par;
void init(int n){
    par.resize(n);
    for(int i = 0; i < n; i++) par[i] = i;
}
int find(int i){
    if(par[i] == i) return i;
    else return par[i] = find(par[i]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    par[a] = b;
}

vector<vector<int>> g;
vector<int> comp;
int dfs_cnt = 0;

void dfs(int u){
    comp[u] = dfs_cnt;
    for(int v : g[u]){
        if(comp[v] == -1) dfs(v);
    }
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    s.push_back(int(1e9+1));
    t.push_back(1);
    int n = (int)s.size();
    vector<pair<int, int>> v;
    vector<pair<int, int>> edges;
    for(int i = 0; i < n; i++){
        v.emplace_back(s[i], 1);
        v.emplace_back(t[i], -1);
        edges.emplace_back(s[i], t[i]);
    }
    sort(v.begin(), v.end());
    int last = 1;
    int sum = 0;
    ll ans = 0;
    for(auto [p, change] : v){
        if(p != last){
            if(sum != 0) edges.emplace_back(last, p), edges.emplace_back(p, last);
            ans += (ll)max(0, sum)*(p-last);
            last = p;
        }
        sum += change;
    }
    set<int> nodes;
    for(auto [u, v] : edges) nodes.insert(u), nodes.insert(v);
    vector<int> vnode(nodes.begin(), nodes.end());
    n = (int)nodes.size();
    g.resize(n);
    for(auto [u, v] : edges){
        int a = int(lower_bound(vnode.begin(), vnode.end(), u)-vnode.begin());
        int b = int(lower_bound(vnode.begin(), vnode.end(), v)-vnode.begin());
        g[a].push_back(b);
    }
    comp.resize(n, -1);
    for(int i = 0; i < n; i++){
        if(comp[i] == -1) dfs(i), dfs_cnt++;
    }
    vector<tuple<int, int, int>> ed;
    for(int i = 1; i < n; i++){
        if(comp[i] != comp[i-1]){
            ed.emplace_back(vnode[i]-vnode[i-1], comp[i], comp[i-1]);
        }
    }
    sort(ed.begin(), ed.end());
    init(dfs_cnt);
    for(auto [c, a, b] : ed){
        if(find(a) != find(b)){
            ans += c;
            merge(a, b);
        }
    }
    return ans;
}

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