Submission #1177533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177533		onlk97	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	465 ms	37992 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
    vector <int> dsu;
    void init(int n){
        for (int i=0; i<=n; i++) dsu.push_back(i);
    }
    int prt(int n){
        if (dsu[n]==n) return n;
        return dsu[n]=prt(dsu[n]);
    }
    void unn(int u,int v){
        dsu[prt(u)]=dsu[prt(v)];
    }
};
long long plan_roller_coaster(vector <int> s,vector <int> t){
    s.push_back(2e9); t.push_back(1);
    int n=s.size();
    set <int> loc;
    for (int i:s) loc.insert(i);
    for (int i:t) loc.insert(i);
    vector <int> vloc;
    for (int i:loc) vloc.push_back(i);
    for (int&i:s) i=lower_bound(vloc.begin(),vloc.end(),i)-vloc.begin();
    for (int&i:t) i=lower_bound(vloc.begin(),vloc.end(),i)-vloc.begin();
    int sz=vloc.size();
    long long in[sz],out[sz];
    for (int i=0; i<sz; i++) in[i]=out[i]=0;
    DSU d; d.init(sz+1);
    for (int i=0; i<n; i++){
        out[s[i]]++; in[t[i]]++;
        d.unn(s[i],t[i]);
    }
    long long ans=0;
    for (int i=0; i+1<sz; i++){
        if (out[i]>in[i]){
            long long dif=out[i]-in[i];
            in[i]+=dif; out[i+1]+=dif;
            ans+=dif*(vloc[i+1]-vloc[i]);
            d.unn(i,i+1);
        } else if (out[i]<in[i]){
            long long dif=in[i]-out[i];
            out[i]+=dif; in[i+1]+=dif;
            d.unn(i,i+1);
        }
    }
    vector <pair <int,int> > vec;
    for (int i=0; i+1<sz; i++) vec.push_back({vloc[i+1]-vloc[i],i});
    sort(vec.begin(),vec.end());
    for (auto i:vec){
        if (d.prt(i.second)!=d.prt(i.second+1)){
            d.unn(i.second,i.second+1);
            ans+=i.first;
        }
    }
    return ans;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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