Submission #789919

#	Time	Username	Problem	Language	Result	Execution time	Memory
789919		alvingogo	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	112 ms	13392 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct DSU{
    vector<int> bo;
    void init(int x){
        bo.resize(x);
        iota(bo.begin(),bo.end(),0);
    }
    int find(int x){
        return bo[x]==x?x:bo[x]=find(bo[x]);
    }
    int merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y){
            return 0;
        }
        bo[x]=y;
        return 1;
    }
}dsu;
const int inf=1e9;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n=s.size();
    vector<pair<int,int> > a(n+1),b(n+1);
    for(int i=0;i<n;i++){
        a[i]={s[i],i};
        b[i]={t[i],i};
    }
    a[n]={inf,n};
    b[n]={1,n};
    n++;
    dsu.init(n);
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    long long sum=0,ax=0;
    for(int i=0;i<n;i++){
        dsu.merge(a[i].sc,b[i].sc);
        sum+=abs(a[i].fs-b[i].fs);
        ax+=a[i].fs;
        ax-=b[i].fs;
    }
    p_q<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    for(int i=0;i+1<n;i++){
        pq.push({2*max(0,min(a[i+1].fs,b[i+1].fs)-max(a[i].fs,b[i].fs)),i});
    }
    while(pq.size()){
        auto h=pq.top();
        pq.pop();
        sum+=dsu.merge(a[h.sc].sc,a[h.sc+1].sc)*h.fs;
    }
    return (sum-ax)/2;
}

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