Submission #276937

#	Time	Username	Problem	Language	Result	Execution time	Memory
276937		MKopchev	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	685 ms	43420 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=2*2e5+42,inf=1e9;
int n;
vector<int> s,t;

int help[nmax],pointer=0;

int pref[nmax];

int parent[nmax];

int root(int node)
{
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
}
void my_merge(int p,int q)
{
    p=root(p);
    q=root(q);
    parent[p]=q;
}

struct edge
{
    int u,v,cost;
};

vector<edge> given;

bool cmp(edge a,edge b)
{
    return a.cost<b.cost;
}

int on[nmax];
long long plan_roller_coaster(vector<int> S, vector<int> T)
{
    S.push_back(inf);
    T.push_back(1);

    n=S.size();

    s=S;
    t=T;

    long long outp=0;

    set<int> noted={1,inf};

    for(int i=0;i<n;i++)
    {
        noted.insert(s[i]);
        noted.insert(t[i]);
    }

    for(auto k:noted)
    {
        pointer++;
        help[pointer]=k;
    }

    for(int i=0;i<=pointer;i++)
    {
        parent[i]=i;
    }

    for(int i=0;i<n;i++)
    {
        int p=lower_bound(help+1,help+pointer+1,s[i])-help;
        int q=lower_bound(help+1,help+pointer+1,t[i])-help;

        my_merge(p,q);

        //cout<<p<<" "<<help[p]<<" "<<q<<" "<<help[q]<<endl;

        pref[p]++;
        pref[q]--;

        on[min(p,q)]++;
        on[max(p,q)]--;
    }

    for(int i=1;i<pointer;i++)
    {
        pref[i]+=pref[i-1];

        on[i]+=on[i-1];
        //cout<<i<<" -> "<<pref[i]<<" "<<help[i]<<" "<<help[i+1]<<endl;

        if(pref[i]>0)outp+=1LL*pref[i]*(help[i+1]-help[i]);

        if(pref[i])parent[root(i)]=root(i+1);


        edge cur;
        cur.u=i;
        cur.v=i+1;
        cur.cost=help[i+1]-help[i];

        given.push_back(cur);
    }

    sort(given.begin(),given.end(),cmp);

    for(auto k:given)
        if(root(k.u)!=root(k.v))
        {
            outp+=k.cost;
            parent[root(k.u)]=root(k.v);
        }

    return outp;
}

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