Submission #209859

#	Time	Username	Problem	Language	Result	Execution time	Memory
209859		alexandra_udristoiu	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	275 ms	16792 KiB

railroad

#include<iostream>
#include<vector>
#include<algorithm>
#include "railroad.h"
#define DIM 400005
using namespace std;
static int w[DIM], st[DIM], dr[DIM], r[DIM];
static pair<int, int> c[DIM];
int cautbin(int x, int n){
    int st = 1, dr = n, mid;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(w[mid] == x){
            return mid;
        }
        if(w[mid] < x){
            st = mid + 1;
        }
        else{
            dr = mid - 1;
        }
    }
}
int rad(int x){
    while(r[x] > 0){
        x = r[x];
    }
    return x;
}
void uneste(int x, int y){
    int r1 = rad(x), r2 = rad(y);
    if(r1 != r2){
        if(r[r1] < r[r2]){
            r[r1] += r[r2];
            r[r2] = r1;
        }
        else{
            r[r2] += r[r1];
            r[r1] = r2;
        }
    }
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n, i, nr, m;
    long long sol = 0;
    s.push_back(1000000001);
    t.push_back(1);
    n = (int) s.size();
    for(i = 0; i < n; i++){
        w[2 * i + 1] = s[i];
        w[2 * i + 2] = t[i];
    }
    sort(w + 1, w + 2 * n + 1);
    nr = 1;
    for(i = 2; i <= n + n; i++){
        if(w[i] != w[nr]){
            w[++nr] = w[i];
        }
    }
    for(i = 1; i <= nr; i++){
        r[i] = -1;
    }
    for(i = 0; i < n; i++){
        s[i] = cautbin(s[i], nr);
        t[i] = cautbin(t[i], nr);
        if(s[i] < t[i]){
            st[ s[i] ]++;
            st[ t[i] ]--;
        }
        else{
            dr[ t[i] ]++;
            dr[ s[i] ]--;
        }
        uneste(s[i], t[i]);
    }
    for(i = 1; i <= nr; i++){
        st[i] += st[i - 1];
        dr[i] += dr[i - 1];
    }
    for(i = 1; i < nr; i++){
        if(st[i] > dr[i]){
            sol += (st[i] - dr[i]) * 1LL * (w[i + 1] - w[i]);
        }
        if(st[i] != dr[i]){
            uneste(i, i + 1);
        }
        c[i] = make_pair(w[i + 1] - w[i], i);
    }
    sort(c, c + nr);
    for(i = 1; i < nr; i++){
        if(rad(c[i].second) != rad(c[i].second + 1) ){
            sol += c[i].first;
            uneste(c[i].second, c[i].second + 1);
        }
    }
    return sol;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:44:19: warning: unused variable 'm' [-Wunused-variable]
     int n, i, nr, m;
                   ^
railroad.cpp: In function 'int cautbin(int, int)':
railroad.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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