제출 #669261

#제출 시각아이디문제언어결과실행 시간메모리
669261flappybirdRoller Coaster Railroad (IOI16_railroad)C++17
100 / 100
230 ms18756 KiB
#include "railroad.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define MAX 404040 #define INF 1000000001 vector<int> all; int deg[MAX]; int N; int p[MAX]; int find(int x) { if (p[x] == x) return x; return p[x] = find(p[x]); } void uni(int x, int y) { x = find(x); y = find(y); p[x] = y; } long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) { N = s.size(); for (auto v : s) all.push_back(v); for (auto v : t) all.push_back(v); all.push_back(INF); all.push_back(0); sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); int X = all.size(); int i; for (i = 0; i < X; i++) p[i] = i; for (auto& v : s) v = lower_bound(all.begin(), all.end(), v) - all.begin(); for (auto& v : t) v = lower_bound(all.begin(), all.end(), v) - all.begin(); for (i = 0; i < N; i++) { deg[s[i]]--; deg[t[i]]++; uni(s[i], t[i]); } deg[0]++; deg[X - 1]--; ll ans = 0; for (i = 1; i < X; i++) { if (deg[i - 1]) { uni(i - 1, i); if (deg[i - 1] < 0) ans += 1ll * -(ll)deg[i - 1] * ((ll)all[i] - all[i - 1]); deg[i] += deg[i - 1]; } } vector<pii> vpi; for (i = 1; i < X; i++) vpi.emplace_back(all[i] - all[i - 1], i); sort(vpi.begin(), vpi.end()); for (auto& [c, v] : vpi) { if (find(v - 1) != find(v)) { uni(v - 1, v); ans += c; } } 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...