Submission #805194

#	Time	Username	Problem	Language	Result	Execution time	Memory
805194		I_Love_EliskaM_	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	836 ms	72980 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<int,int>
#define f first
#define s second

struct DSU {
    vector<int> p,sz;
    DSU(int n) {
        forn(i,n) p.pb(i), sz.pb(1);
    }
    int get(int u) {
        return p[u]==u?u:get(p[u]);
    }
    void uni(int u, int v) {
        u=get(u),v=get(v);
        if (u==v) return;
        if (sz[u]<sz[v]) swap(u,v);
        sz[u]+=sz[v];
        p[v]=u;
    }
};

struct edge {
    int w, u, v;
};
bool foo(edge a, edge b) {
    return a.w<b.w;
}

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

    int mx=0, mn=1e9+7; 
    for(auto&x:s) mx=max(mx,x), mn=min(mn,x);
    for(auto&x:t) mx=max(mx,x), mn=min(mn,x);
    s.pb(mx);
    t.pb(mn);
    ++n;

    int m=0;
    set<int> st; forn(i,n) st.insert(s[i]), st.insert(t[i]);
    map<int,int> c, d;
    for(auto&x:st) {
        d[m]=x;
        c[x]=m++;
    }

    vector<int> pr(m);
    forn(i,n) s[i]=c[s[i]], t[i]=c[t[i]];

    DSU dsu(m);
    forn(i,n) {
        pr[t[i]]++;
        pr[s[i]]--;
        dsu.uni(s[i],t[i]);
    }
    for(int i=1; i<m; ++i) pr[i]+=pr[i-1];

    ll ans=0;
    forn(i,m) {
        if (pr[i]<0) ans-=1ll*pr[i]*(d[i+1]-d[i]);
        if (pr[i]) dsu.uni(i,i+1);
    }
    vector<edge> e;
    forn(i,m-1) {
        if (dsu.get(i)!=dsu.get(i+1)) e.pb({d[i+1]-d[i],i,i+1});
    }
    sort(all(e),foo);
    for(auto&x:e) {
        if (dsu.get(x.u)==dsu.get(x.v)) continue;
        dsu.uni(x.u,x.v);
        ans+=x.w;
    }
    return ans;
}

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