| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 562955 | hoanghq2004 | Roller Coaster Railroad (IOI16_railroad) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long cost;
int in[400010], out[400010];
struct railroad {
int s, t;
} r[200010];
vector <int> data;
vector <pair <int, pair <int, int> > > edge;
void compress() {
for (int i = 1; i <= n; ++i) {
data.push_back(r[i].s);
data.push_back(r[i].t);
}
data.push_back(0);
sort(data.begin(), data.end());
data.erase(unique(data.begin(), data.end()), data.end());
m = data.size() - 1;
for (int i = 1; i <= n; ++i) {
r[i].s = lower_bound(data.begin(), data.end(), r[i].s) - data.begin();
r[i].t = lower_bound(data.begin(), data.end(), r[i].t) - data.begin();
}
}
int l[400010], h[400010];
int cnt;
int Find(int u) {
return (u == l[u] ? u : l[u] = Find(l[u]));
}
void Union(int u, int v) {
if ((u = Find(u)) == (v = Find(v))) return;
if (h[u] < h[v]) swap(u, v);
h[u] += h[v];
l[v] = u;
--cnt;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &r[i].s, &r[i].t);
compress();
for (int i = 1; i <= m; ++i) l[i] = i, h[i] = 1;
cnt = m;
for (int i = 1; i <= n; ++i) {
Union(r[i].s, r[i].t);
++out[r[i].s], ++in[r[i].t];
}
Union(1, m);
++in[1], ++out[m];
for (int i = m; i >= 2; --i) {
int add = abs(in[i] - out[i]);
if (add == 0) continue;
Union(i, i - 1);
if (in[i] > out[i]) {
out[i] += add;
in[i - 1] += add;
cost += 1ll * add * (data[i] - data[i - 1]);
}
else {
in[i] += add;
out[i - 1] += add;
}
}
for (int i = 1; i < m; ++i)
if (Find(i) != Find(i + 1)) {
edge.push_back({data[i + 1] - data[i], {i, i + 1}});
}
sort(edge.begin(), edge.end());
for (int i = 0; i < edge.size(); ++i)
if (Find(edge[i].second.first) != Find(edge[i].second.second)) cost += edge[i].first, Union(edge[i].second.first, edge[i].second.second);
printf("%lld", cost);
}