Submission #1192718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192718		TAMREF	Roller Coaster Railroad (IOI16_railroad)	C++20	0 / 100	2099 ms	76532 KiB

railroad

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<int>> G, H;
vector<int> dt, ft, scc;
int clk, n_scc;

void dfs(int x) {
    dt[x] = ++clk;
    for(int u : G[x]) {
        if(dt[u]) continue;
        dfs(u);
    }
    ft.push_back(x);
}

void rdfs(int x) {
    for(int u : H[x]) {
        if(scc[u]) continue;
        scc[u] = scc[x];
        rdfs(u);
    }
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = s.size();

    vector<int> cmp;
    cmp.push_back(1);
    for(int i = 0; i < n; i++) {
        cmp.push_back(s[i]); cmp.push_back(t[i]);
    }
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());

    int m = cmp.size();

    G.resize(m);
    H.resize(m);
    dt.resize(m);
    scc.resize(m);

    for(int i = 0; i < m-1; i++) {
        G[i].push_back(i+1);
        H[i+1].push_back(i);
    }

    for(int i = 0; i < n; i++) {
        int a = lower_bound(cmp.begin(), cmp.end(), s[i]) - cmp.begin();
        int b = lower_bound(cmp.begin(), cmp.end(), t[i]) - cmp.begin();
        G[a].push_back(b);
        H[b].push_back(a);
    }

    for(int i = 0; i < m; i++) {
        if(!dt[i]) dfs(i);
    }

    reverse(ft.begin(), ft.end());
    for(int i : ft) {
        if(!scc[i]) {
            scc[i] = ++n_scc;
            rdfs(i);
        }
    }

    vector<vector<int>> gscc(n_scc);
    for(int i = 0; i < m; i++) {
        for(int j : G[i]) {
            gscc[scc[i]-1].push_back(scc[j]-1);
        }
    }

    for(int i = 0; i < n_scc; i++) {
        sort(gscc[i].begin(), gscc[i].end());
        gscc[i].erase(unique(gscc[i].begin(), gscc[i].end()), gscc[i].end());
    }

    int now = 1, cnt = 0;
    for(; ;) {
        if(gscc[now].size() > 1) return 3;
        if(gscc[now].empty()) break;
        ++cnt;
        now = gscc[now][0];
    }

    return cnt == n_scc ? 0 : 3;
}

#ifdef TAMREF
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<int> s(n), t(n);
    for(int i = 0; i < n; i++) {
        cin >> s[i] >> t[i];
    }
    cout << plan_roller_coaster(s, t) << '\n';
}
#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: 0 / 30
• Subtask 4: 0 / 36