Submission #119748

#	Time	Username	Problem	Language	Result	Execution time	Memory
119748		dorijanlendvaj	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	1958 ms	72016 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
using namespace std;
const int MOD=1000000007,N=400010;
const char en='\n';
const ll LLINF=1ll<<60;
int par[N];
ll ans;
unordered_map<int,int> ma;

int fin(int a)
{
	if (a==par[a]) return a;
	return par[a]=fin(par[a]);
}

void merge(int a,int b,int c)
{
	a=fin(a);
	b=fin(b);
	if (a==b) return;
	ans+=c;
	par[a]=b;
}

bool debug=0;

ll plan_roller_coaster(vi s, vi t) {
	//if (debug) cout<<"startao"<<endl;
    int n = s.size()+1;
    s.pb(2e9);
    t.pb(1);
    set<int> x;
    for (auto e: s) x.insert(e);
    for (auto e: t) x.insert(e);
    for (int i=0;i<x.size();i++) par[i]=i;
    int i=0;
    for (auto e: x)
    {
    	ma[e]=i++;
    }
    //if (debug) cout<<"tu sam"<<endl;
    for (int i=0;i<n;++i) merge(ma[s[i]],ma[t[i]],0);
    map<int,int> maa;
    for (int i=0;i<n;++i) ++maa[s[i]],--maa[t[i]];
    int last=1,bal=0;
    //if (debug) cout<<"i tu sam"<<endl;
    for (auto a: maa)
    {
    	if (debug) cout<<last<<' '<<a.x<<' '<<bal<<en;
        if (bal) merge(ma[a.x],ma[last],0);
        ans+=max(0,bal)*1ll*(a.x-last);
        bal+=a.y;
        last=a.x;
    }
    if (debug) cout<<"finished random loop with ans="<<ans<<endl;
    vector<pair<int,pii>> v;
    auto it=x.begin();
    auto it1=it;
    ++it1;
    while (it1!=x.end())
    {
    	int a=*it,b=*it1;
    	v.pb({b-a,{ma[a],ma[b]}});
    	++it;
    	++it1;
    	if (debug) cout<<"from "<<a<<" to "<<b<<" with cost="<<b-a<<endl;
    }
    sort(v.begin(),v.end());
    for (auto a: v) merge(a.y.x,a.y.y,a.x);
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<x.size();i++) par[i]=i;
                  ~^~~~~~~~~

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