Submission #1189318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189318		anmattroi	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	426 ms	54164 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 200005
using namespace std;
using ii = pair<int, int>;

vector<int> adj[2*maxn];
int cl[2*maxn];

void dfs(int u) {
    cl[u] = 1;
    for (int v : adj[u])
        if (!cl[v]) dfs(v);
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    s.emplace_back(1e9);
    t.emplace_back(1);

    int n = s.size();
    map<int, int> nho;

    for (int i = 0; i < n; i++) {
        ++nho[s[i]];
        --nho[t[i]];
    }
    int last = 0;
    for (auto &i : nho) last = (i.se += last);

    for (auto [u, v] : nho)if (v > 0) return 1;
    vector<int> a;
    for (int i = 0; i < n; i++) {
        a.emplace_back(s[i]);
        a.emplace_back(t[i]);
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    int m = a.size();

    for (int i = 0; i < n; i++) {
        int p = lower_bound(a.begin(), a.end(), s[i]) - a.begin(),
            q = lower_bound(a.begin(), a.end(), t[i]) - a.begin();
        adj[p].emplace_back(q);
    }
    for (auto [u, v] : nho)
    if (v < 0) {
        int p = lower_bound(a.begin(), a.end(), u) - a.begin();
        adj[p].emplace_back(p+1);
    }
    dfs(0);
    for (int i = 0; i < m; i++) if (!cl[i]) return 1;
    return 0;
}

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