Submission #292530

#	Time	Username	Problem	Language	Result	Execution time	Memory
292530		shayan_p	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	705 ms	35556 KiB

railroad

// Oh damn! Suddenly you're free to fly...
 
#include<bits/stdc++.h>
#include "railroad.h"
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int maxn = 4e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
int pr[maxn];
 
int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
bool mrg(int a, int b){
    if( (a = fnd(a)) == (b = fnd(b)) )
	return 0;
    if(pr[a] > pr[b])
	swap(a, b);
    pr[a]+= pr[b];
    pr[b] = a;
    return 1;
}
 

ll plan_roller_coaster(vector<int> a, vector<int> b){
    memset(pr, -1, sizeof pr);
    
    int n = sz(a);
    map<int, int> mp;
    mp[0]++; // first of all
    for(int x : a)
	mp[x]--;
    for(int x : b)
	mp[x]++;
 
    vector<int> tot;
    for(int x : a)
	tot.PB(x);
    for(int x : b)
	tot.PB(x);
    tot.PB(0);
    sort(tot.begin(), tot.end());
    tot.resize( unique(tot.begin(), tot.end()) - tot.begin() );
    
    auto comp = [&](int x){
		    return lower_bound(tot.begin(), tot.end(), x) - tot.begin();
		};
    int mrgs = 0;
    for(int i = 0; i < n; i++){
	mrgs+= mrg(comp(a[i]), comp(b[i]));
    }

    ll ans = 0;
    int sum = 0, ID = 0;
    for(auto it = mp.begin(); it != mp.end(); it++, ID++){
	sum+= it->S;
	if(sum < 0)
	    ans+= 1ll * abs(sum) * (tot[ID+1] - tot[ID]);
	if(sum != 0)
	    mrgs+= mrg(ID, ID + 1);
    }
    vector< pair<int, pii> > eds;
    for(int i = 0; i < sz(tot)-1; i++){
	eds.PB({tot[i+1] - tot[i], {i, i+1}});
    }
    sort(eds.begin(), eds.end());
    for(auto it : eds){
	if(mrg(it.S.F, it.S.S))
	    ans+= it.F;
    }    
    return ans;
}

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