제출 #388614

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388614		ParsaAlizadeh	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	258 ms	17224 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;

typedef long long ll;

struct DSU {
    int n;
    vector<int> par;

    DSU(int n) : n(n), par(n, -1) {}

    int find(int u) {
        return par[u] == -1 ? u : par[u] = find(par[u]);
    }

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

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    int const n = (int) s.size();
    vector<int> comp(begin(s), end(s));
    comp.insert(end(comp), begin(t), end(t));
    sort(begin(comp), end(comp));
    comp.erase(unique(begin(comp), end(comp)), end(comp));
    
    int const m = (int) comp.size();
    vector<int> ps(m);
    DSU dsu(m);
    ll ans = 0;

    for (int i = 0; i < n; i++) {
        int l = lower_bound(begin(comp), end(comp), s[i]) - begin(comp);
        int r = lower_bound(begin(comp), end(comp), t[i]) - begin(comp);
        ps[l]++; ps[r]--;
        dsu.merge(l, r);
    }
    ps[m - 1]++; ps[0]--;
    partial_sum(begin(ps), end(ps), begin(ps));
    
    vector<pair<int, int>> edges;
    for (int i = 0; i + 1 < m; i++) {
        if (ps[i] > 0)
            ans += (ll) ps[i] * (comp[i + 1] - comp[i]);
        if (ps[i] != 0)
            dsu.merge(i, i + 1);
        edges.emplace_back(comp[i + 1] - comp[i], i);
    }
    sort(begin(edges), end(edges));
    for (auto & e : edges) {
        if (dsu.merge(e.second, e.second + 1))
            ans += e.first;
    }
    return ans;
}

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