Submission #1256271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256271		biank	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	132 ms	13328 KiB

railroad

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

const int INF = 1e9 + 9;

struct DSU {
    vi p;
    DSU(int n) : p(n, -1) {}
    int find(int x) {
        if (p[x] < 0) return x;
        return p[x] = find(p[x]);
    }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (p[x] > p[y]) swap(x, y);
        p[x] += p[y], p[y] = x;
        return true;
    }
};

ll plan_roller_coaster(vi s, vi t) {
    s.pb(INF), t.pb(1);
    int n = sz(s);
    vi vals = s;
    forn(i, n) vals.pb(t[i]);
    sort(all(vals));
    vals.erase(unique(all(vals)), end(vals));
    auto pos = [&](int x) {
        return int(lower_bound(all(vals), x) - begin(vals));
    };
    forn(i, n) s[i] = pos(s[i]), t[i] = pos(t[i]);
    const int m = sz(vals);
    DSU dsu(m);
    forn(i, n) dsu.unite(s[i], t[i]);
    vi delta(m);
    forn(i, n) delta[s[i]]++, delta[t[i]]--;
    vector<pair<ll, int>> edges;
    ll pref = 0LL, ret = 0LL;
    forn(i, m - 1) {
        int dist = vals[i + 1] - vals[i];
        pref += delta[i];
        ret += max(0LL, pref) * dist;
        if (pref != 0LL) dsu.unite(i, i + 1);
        else edges.eb(dist, i);
    }
    sort(all(edges));
    for (auto [w, i] : edges) {
        if (dsu.unite(i, i + 1)) ret += w;
    }
    return ret;
}

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