Submission #1021528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021528		Wansur	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	525 ms	78448 KiB

railroad

#include <bits/stdc++.h>
#define ent '\n'

typedef long long ll;
using namespace std;
const int maxn = 1e6+12;

vector<int> g[maxn];
int pref[maxn];
int used[maxn];
int n, m;
int timer;
int p[maxn];

void dfs(int v){
    used[v] = timer;
    for(int to:g[v]){
        if(!used[to]){
            dfs(to);
        }
    }
}

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

long long plan_roller_coaster(vector<int> s, vector<int> t){
    n = s.size();
    vector<int> uni = {1, (int)1e9+1};
    map<int, int> val;
    for(int x:s){
        uni.push_back(x);
    }
    for(int x:t){
        uni.push_back(x);
    }
    sort(uni.begin(), uni.end());
    uni.resize(unique(uni.begin(), uni.end()) - uni.begin());
    for(int i=0;i<uni.size();i++){
        val[uni[i]] = i + 1;
    }
    m = uni.size();
    for(int i=0;i<n;i++){
        s[i] = val[s[i]];
        t[i] = val[t[i]];
        if(s[i] > t[i]){
            pref[t[i]]--, pref[s[i]]++;
        }
        else{
            pref[s[i]]++, pref[t[i]]--;
        }
        g[s[i]].push_back(t[i]);
    }
    ll ans = 0;
    pref[1]--, pref[m]++;
    for(int i=1;i<m;i++){
        pref[i] += pref[i-1];
        if(pref[i] > 0){
            ans += pref[i] * 1ll * (uni[i] - uni[i-1]);
            g[i+1].push_back(i);
        }
        if(pref[i] < 0){
            g[i].push_back(i+1);
        }
    }
    g[1].push_back(m);
    for(int i=1;i<=m;i++){
        if(!used[i]){
            timer++;
            dfs(i);
        }
        p[i] = i;
    }
    vector<pair<int, pair<int, int>>> e;
    for(int i=1;i<=m;i++){
        for(int to:g[i]){
            if(used[i] == used[to]) p[get(i)] = get(to);
        }
        if(i < m && used[i] != used[i+1]){
            e.push_back({uni[i] - uni[i-1], {i, i+1}});
        }
    }
    sort(e.begin(), e.end());
    for(auto [w, t]:e){
        auto [v, u] = t;
        if(get(v) != get(u)){
            p[get(v)] = get(u);
            ans += w;
        }
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<uni.size();i++){
      |                 ~^~~~~~~~~~~

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