Submission #1323533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323533		k1r1t0	Roller Coaster Railroad (IOI16_railroad)	C++20	30 / 100	267 ms	37512 KiB

railroad

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vi = vector<int>;

const int N = 410000;
const int INF = (int)(2e9);

int n, m, b[N];
bool w[N];
vi zip, g[N];

void dfs(int v) {
    if (w[v]) return;
    w[v] = true;
    for (int u : g[v])
        dfs(u);
}

ll plan_roller_coaster(vi s, vi t) {
    s.push_back(INF);
    t.push_back(1);
    n = s.size();
    for (int i = 0; i < n; i++) {
        zip.push_back(s[i]);
        zip.push_back(t[i]);
    }
    sort(begin(zip), end(zip));
    zip.erase(unique(begin(zip), end(zip)), end(zip));
    m = zip.size();
    for (int i = 0; i < n; i++) {
        s[i] = lower_bound(begin(zip), end(zip), s[i]) - begin(zip);
        t[i] = lower_bound(begin(zip), end(zip), t[i]) - begin(zip);
    }
    for (int i = 0; i < n; i++) {
        g[s[i]].push_back(t[i]);
        g[t[i]].push_back(s[i]);
    }
    for (int i = 0; i < n; i++) {
        b[s[i]]++;
        b[t[i]]--;
    }
    for (int i = 1; i < m; i++)
        b[i] += b[i - 1];
    for (int i = 0; i < m; i++)
        if (b[i] > 0)
            return 1;
        else if (b[i] < 0) {
            g[i].push_back(i + 1);
            g[i + 1].push_back(i);
        }
    for (int i = 0; i < m; i++)
        w[i] = false;
    dfs(0);
    for (int i = 0; i < m; i++)
        if (!w[i])
            return 1;
    return 0;
}





























#ifdef LOCAL

int main() {
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> s(n), t(n);
    for (int i = 0; i < n; ++i)
        assert(2 == scanf("%d%d", &s[i], &t[i]));
    long long ans = plan_roller_coaster(s, t);
    printf("%lld\n", ans);
    return 0;
}

#endif

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