Submission #620104

#	Time	Username	Problem	Language	Result	Execution time	Memory
620104		definitelynotmee	Roller Coaster Railroad (IOI16_railroad)	C++98	100 / 100	696 ms	57404 KiB

railroad

#include<bits/stdc++.h>
#include"railroad.h"
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;

struct edge{
    ll a, b, w;
    bool operator<(edge c) const{
        return w < c.w;
    }
};

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = s.size();
    set<int> S;
    S.insert(0);
    S.insert(INF);
    map<int,int> tr;
    
    for(int i = 0; i < n; i++){
        S.insert(s[i]);
        S.insert(t[i]);
    }

    for(int i : S)
        tr[i] = tr.size();
    
    int m = tr.size();
    
    vector<int> delta(m);
    vector<ll> og(m);

    for(pii i : tr){
        og[i.ss] = i.ff;
    }
    for(int& i : s)
        i = tr[i];
    for(int& i : t)
        i = tr[i];
    
    vector<int> pai(m);
    iota(all(pai),0);

    auto find =[&](int id, auto f){
        if(pai[id] == id)
            return id;
        return pai[id] = f(pai[id],f);
    };

    auto onion =[&](int a, int b){
        a = find(a,find);
        b = find(b,find);
        if(a == b)
            return false;
        pai[a] = b; 
        return true;
    };

    ll ahead = 1;
    ll resp = 0;

    for(int i = 0; i < n; i++){
        delta[s[i]]--;
        delta[t[i]]++;
        onion(s[i],t[i]);
    }
    
    vector<edge> cand;

    for(int i = 0; i < m-1; i++){
        ahead+=delta[i];
        if(ahead!=0){
            resp+=max(0ll,-ahead*(og[i+1]-og[i]));
            onion(i,i+1);
        } else cand.push_back({i,i+1,og[i+1]-og[i]});
    }
    
    sort(all(cand));

    for(edge i : cand){
        if(onion(i.a,i.b))
            resp+=i.w;
    }

    return resp;
}

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