Submission #380393

#	Time	Username	Problem	Language	Result	Execution time	Memory
380393		denkendoemeer	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	218 ms	15180 KiB

railroad

#include<bits/stdc++.h>
#include "railroad.h"
const int inf=2e9;
#define ll long long
using namespace std;
vector<int>nex;
int findt(int node)
{
    if (nex[node]!=-1)
        return nex[node]=findt(nex[node]);
    return node;
}
bool onion(int x,int y)
{
    x=findt(x);
    y=findt(y);
    if (x==y)
        return 0;
    nex[y]=x;
    return 1;
}
ll plan_roller_coaster(vector<int>s,vector<int>t)
{
    s.push_back(inf);
    t.push_back(1);
    int n=s.size();
    vector<int>aux=s;
    aux.insert(aux.end(),t.begin(),t.end());
    sort(aux.begin(),aux.end());
    aux.erase(unique(aux.begin(),aux.end()),aux.end());
    int m=aux.size();
    nex.resize(m,-1);
    vector<int>b(m--);
    int i;
    for(i=0;i<n;i++){
        int st=lower_bound(aux.begin(),aux.end(),s[i])-aux.begin();
        int dr=lower_bound(aux.begin(),aux.end(),t[i])-aux.begin();
        onion(st,dr);
        ++b[st];
        --b[dr];
    }
    for(i=0;i<m;i++)
        b[i+1]+=b[i];
    vector<pair<int,int>>pi;
    ll ans=0;
    for(i=0;i<m;i++){
        ll sum=aux[i+1]-aux[i];
        if (b[i]){
            onion(i,i+1);
            if (b[i]>0)
                ans=ans+b[i]*sum;
        }
        else
            pi.push_back({sum,i});
    }
    sort(pi.begin(),pi.end());
    for(auto it:pi)
        if (onion(it.second,it.second+1))
            ans+=it.first;
    return ans;
}

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