제출 #426366

#제출 시각아이디문제언어결과실행 시간메모리
426366timmyfengRoller Coaster Railroad (IOI16_railroad)C++17
34 / 100
2082 ms49968 KiB
#include <bits/stdc++.h> using namespace std; map<int, int> par; int find(int u) { if (par.count(u) > 0) { return par[u] = find(par[u]); } else { return u; } } bool unite(int u, int v) { u = find(u), v = find(v); if (u != v) { par[u] = v; return true; } return false; } long long plan_roller_coaster(vector<int> s, vector<int> t) { s.push_back(INT_MAX), t.push_back(1); int n = s.size(); map<int, int> events; for (int i = 0; i < n; ++i) { unite(s[i], t[i]); ++events[s[i]]; --events[t[i]]; } long long ans = 0; int prv = 1, balance = 0; vector<array<int, 3>> edges; for (auto [x, d] : events) { if (balance != 0) { ans += (long long) (x - prv) * max(0, balance); unite(prv, x); } edges.push_back({x - prv, prv, x}); balance += d; prv = x; } sort(edges.begin(), edges.end()); for (auto [w, u, v] : edges) { if (unite(u, v)) { ans += w; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...