Submission #1189318

#TimeUsernameProblemLanguageResultExecution timeMemory
1189318anmattroiRoller Coaster Railroad (IOI16_railroad)C++17
30 / 100
426 ms54164 KiB
#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
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...