Submission #329721

#	Time	Username	Problem	Language	Result	Execution time	Memory
329721		two_sides	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	223 ms	14940 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

struct dsu {
    vector <int> par;

    dsu(int n) {
        par.resize(n);
        iota(begin(par), end(par), 0);
    }

    int find_set(int u) {
        return u == par[u] ?
        u : par[u] = find_set(par[u]);
    }

    bool union_set(int u, int v) {
        u = find_set(u);
        v = find_set(v);
        if (u == v) return false;
        par[v] = u; return true;
    }
};

struct edge {
    int u, v, w;
};

long long plan_roller_coaster
(vector <int> s, vector <int> t) {
    int n = s.size();
    long long ans = 0;
    vector <int> vals;
    vector <edge> lst;
    for (int x : s) vals.push_back(x);
    for (int x : t) vals.push_back(x);
    sort(begin(vals), end(vals));
    vals.erase(unique(begin(vals),
    end(vals)), end(vals));
    vector <int> bal(vals.size() + 1);
    dsu ds(vals.size());
    for (int i = 0; i < n; i++) {
        s[i] = lower_bound(vals.begin(),
        vals.end(), s[i]) - vals.begin();
        t[i] = lower_bound(vals.begin(),
        vals.end(), t[i]) - vals.begin();
        bal[s[i]]++; bal[t[i]]--;
        ds.union_set(s[i], t[i]);
    }
    int m = vals.size(), cur = 1;
    for (int i = m - 1; i > 0; i--) {
        cur += bal[i];
        if (cur < 0) {
            ans += (long long)cur * 
            (vals[i - 1] - vals[i]);
            ds.union_set(i - 1, i);
        }
        else if (cur > 0)
            ds.union_set(i - 1, i);
        else lst.push_back({i - 1, i,
            vals[i] - vals[i - 1]});
    }
    sort(lst.begin(), lst.end(),
    [](const edge &p, const edge &q) {
        return p.w < q.w;
    });
    for (const edge &e : lst)
        if (ds.union_set(e.u, e.v))
            ans += e.w;
    return ans;
}

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