Submission #1197658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197658		vjudge2	Roller Coaster Railroad (IOI16_railroad)	C++20	30 / 100	163 ms	31304 KiB

railroad

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

using i32 = int32_t;
#define int long long

const int MAXN = 400005;
int p[MAXN], sz[MAXN], diff[MAXN];

int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}

bool merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return false;
    if (sz[u] < sz[v]) swap(u, v);
    p[v] = u, sz[u] += sz[v];
    return true;
}

int plan_roller_coaster(std::vector<i32> s, std::vector<i32> t) {
    int n = (int) s.size();
    vector<int> disc;
    for (int i = 0; i < n; i++) {
        disc.push_back(s[i]);
        disc.push_back(t[i]);
    }
    sort(disc.begin(), disc.end());
    disc.erase(unique(disc.begin(), disc.end()), disc.end());
    for (int i = 1; i <= (int) disc.size() + 1; i++) p[i] = i, sz[i] = 1;
    for (int i = 0; i < n; i++) {
        // cout << s[i] << " " << t[i] << '\n';
        s[i] = lower_bound(disc.begin(), disc.end(), s[i]) - disc.begin() + 1;
        t[i] = lower_bound(disc.begin(), disc.end(), t[i]) - disc.begin() + 1;
        merge(s[i], t[i]);
        // cout << "merge: " << s[i] << " " << t[i] << '\n';
        diff[s[i]]++, diff[t[i]]--;
    }
    int sz = disc.size();
    merge(sz + 1, 1);
    disc.push_back(1e9 + 1);
    diff[sz + 1]++, diff[1]--;
    for (int i = 1; i <= sz; i++) diff[i + 1] += diff[i];
    int ans = 0;
    for (int i = 1; i <= sz; i++) {
        if (diff[i] != 0) merge(i, i + 1);
        if (diff[i] > 0) ans += diff[i] * (disc[i + 1] - disc[i]);
    }
    vector<array<int, 3>> edge;
    for (int i = 1; i <= sz; i++) edge.push_back({i, i + 1, disc[i + 1] - disc[i]});
    sort(edge.begin(), edge.end(), [] (auto x, auto y) {
        return x[2] < y[2];
    });
    for (auto& [u, v, w] : edge) if (merge(u, v)) ans += w;
    return ans;
}

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: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 30 / 30
• Subtask 4: 0 / 36