Submission #591511

#	Time	Username	Problem	Language	Result	Execution time	Memory
591511		yutabi	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	127 ms	12624 KiB

railroad

#include "railroad.h"


#include <bits/stdc++.h>
using namespace std;


#define pb push_back


typedef long long ll;
typedef pair <int,int> ii;



vector <int> DSU;


int find_parent(int a)
{
    if(DSU[a]==a)
    {
        return a;
    }

    return DSU[a]=find_parent(DSU[a]);
}

bool make_union(int a, int b)
{
    a=find_parent(a);
    b=find_parent(b);

    if(a==b)
    {
        return 0;
    }

    DSU[b]=a;

    return 1;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
    int n = (int) s.size();


    vector <ii> nw_s;
    vector <ii> nw_t;

    for(int i=0;i<n;i++)
    {
        nw_s.pb(ii(s[i],i));
        nw_t.pb(ii(t[i],i));
    }

    vector <ii> nw;

    sort(nw_s.begin(),nw_s.end());
    sort(nw_t.begin(),nw_t.end());

    for(int i=0;i<n-1;i++)
    {
        nw.pb(ii(nw_t[i].second,nw_s[i+1].second));
    }

    nw.pb(ii(nw_t[n-1].second,nw_s[0].second));


    DSU=vector <int> (n);

    for(int i=0;i<n;i++)
    {
        DSU[i]=i;
    }

    ll ans=0;

    priority_queue <ii> pq;

    for(int i=0;i<n;i++)
    {
        make_union(nw[i].first,nw[i].second);

        if(i!=n-1)
        {
            ans+=max(t[nw[i].first]-s[nw[i].second],0);

            pq.push(ii(i,max(t[nw[i+1].first]-s[nw[i].second],0)+max(t[nw[i].first]-s[nw[i+1].second],0)-max(t[nw[i].first]-s[nw[i].second],0)-max(t[nw[i+1].first]-s[nw[i+1].second],0)));
        }
    }

    for(int i=0;i<n;i++)
    {
        //printf("%d %d\n",t[nw[i].first],s[nw[i].second]);
    }

    while(pq.size())
    {
        int ptr=pq.top().first;
        int num=pq.top().second;

        pq.pop();

        if(make_union(nw[ptr].first,nw[ptr+1].first))
        {
            ans+=max(0,num);
        }
    }

    return ans;
}

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