Submission #1217936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217936		thinknoexit	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	210 ms	58604 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 400400;
struct Edge {
    int u, v, w;
    bool operator < (const Edge& o) const {
        return w < o.w;
    }
};
vector<Edge> e;
bool vis[N];
int n, p[N];
ll qs[N];
vector<int> adj[N];
int fr(int i) {
    return p[i] == i ? i : p[i] = fr(p[i]);
}
void dfs(int v, int rt) {
    vis[v] = 1;
    p[fr(v)] = rt;
    for (auto& x : adj[v]) if (!vis[x]) dfs(x, rt);
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
    s.push_back(1e9), t.push_back(1);
    n = (int)s.size();
    vector<int> compress;
    for (int i = 0;i < n;i++) {
        compress.push_back(s[i]);
        compress.push_back(t[i]);
    }
    sort(compress.begin(), compress.end());
    compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
    for (int i = 0;i < n;i++) {
        s[i] = lower_bound(compress.begin(), compress.end(), s[i]) - compress.begin();
        t[i] = lower_bound(compress.begin(), compress.end(), t[i]) - compress.begin();
        qs[s[i]]++;
        qs[t[i]]--;
        adj[s[i]].push_back(t[i]);
    }
    ll ans = 0;
    int sz = compress.size();
    for (int i = 0;i < sz - 1;i++) {
        if (qs[i] > 0) {
            // i -> i+1
            adj[i].push_back(i + 1);
            adj[i + 1].push_back(i);
            ans += qs[i] * (compress[i + 1] - compress[i]);
        }
        else if (qs[i] < 0) {
            adj[i + 1].push_back(i);
            adj[i].push_back(i + 1);
        }
        qs[i + 1] += qs[i];
    }
    for (int i = 0;i < sz;i++) p[i] = i;
    for (int i = 0;i < sz;i++) {
        if (!vis[i]) dfs(i, fr(i));
    }
    for (int i = 0;i < sz - 1;i++) {
        e.push_back({ i, i + 1, compress[i + 1] - compress[i] });
    }
    sort(e.begin(), e.end());
    for (auto& x : e) {
        int pu = fr(x.u), pv = fr(x.v);
        if (pu == pv) continue;
        p[pu] = pv;
        ans += x.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: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36