Submission #1189319

#TimeUsernameProblemLanguageResultExecution timeMemory
1189319anmattroiRoller Coaster Railroad (IOI16_railroad)C++17
100 / 100
426 ms33160 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>; int par[2*maxn]; struct edge { int u, v, l; edge() {} edge(int _u, int _v, int _l) : u(_u), v(_v), l(_l) {} bool operator < (const edge &other) const { return l < other.l; } }; vector<edge> edges; int find_set(int v) { return par[v] < 0 ? v : par[v] = find_set(par[v]); } void union_set(int u, int v) { u = find_set(u); v = find_set(v); if (u == v) return; if (par[u] < par[v]) swap(u, v); par[v] += par[u]; par[u] = 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); 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 < m; i++) par[i] = -1; 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(); union_set(p, q); } int64_t ans = 0; for (auto &i : nho) if (i.se > 0) { int p = lower_bound(a.begin(), a.end(), i.fi) - a.begin(); ans += 1LL * (a[p+1] - a[p]) * i.se; union_set(p+1, p); i.se = 0; } for (auto [u, v] : nho) if (v < 0) { int p = lower_bound(a.begin(), a.end(), u) - a.begin(); union_set(p, p+1); } for (int i = 0; i < m-1; i++) edges.emplace_back(i, i+1, a[i+1]-a[i]); sort(edges.begin(), edges.end()); for (auto [u, v, l] : edges) if (find_set(u) != find_set(v)) { union_set(u, v); ans += l; } 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
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...