Submission #600519

#	Time	Username	Problem	Language	Result	Execution time	Memory
600519		cheissmart	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	232 ms	19620 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

struct DSU {
    vi p, sz;
    DSU(int n) {
        p = vi(n), sz = vi(n, 1), iota(ALL(p), 0);
    }
    int find(int u) {
        return p[u] == u ? u : p[u] = find(p[u]);
    }
    void unite(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return;
        if(sz[u] > sz[v]) swap(u, v);
        p[u] = v, sz[v] += sz[u];
    }
};  

ll plan_roller_coaster(vi s, vi t) {
    int n = SZ(s);
    vi compress;
    for(int i:s) compress.PB(i);
    for(int i:t) compress.PB(i);
    compress.PB(1), compress.PB(1e9);
    sort(ALL(compress)), compress.resize(unique(ALL(compress)) - compress.begin());
    int m = SZ(compress);
    vi aux(m);

    DSU dsu(m);
    for(int i = 0; i < n; i++) {
        int l = lower_bound(ALL(compress), s[i]) - compress.begin();
        int r = lower_bound(ALL(compress), t[i]) - compress.begin();
        aux[l]++, aux[r]--;
        dsu.unite(l, r);
    }
    ll ans = 0;
    for(int i = 0; i < m - 1; i++) {
        if(aux[i] > 1) {
            ans += 1LL * (aux[i] - 1) * (compress[i + 1] - compress[i]);
            dsu.unite(i, i + 1);
        } else if(aux[i] < 1) {
            dsu.unite(i, i + 1);
        }
        aux[i + 1] += aux[i];
    }
    V<pair<ll, pi>> es;
    for(int i = 0; i < m - 1; i++)
        es.EB(compress[i + 1] - compress[i], pi(i, i + 1));
    sort(ALL(es));
    for(auto[w, uv]:es) {
        auto [u, v] = uv;
        if(dsu.find(u) != dsu.find(v)) {
            dsu.unite(u, v);
            ans += w;
        }
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(vi, vi)':
railroad.cpp:68:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for(auto[w, uv]:es) {
      |             ^
railroad.cpp:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         auto [u, v] = uv;
      |              ^

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