| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 332429 | a14789654 | Roller Coaster Railroad (IOI16_railroad) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
int par[MAXN], n, in[MAXN], out[MAXN], a[MAXN], b[MAXN];
vector <int> V;
int pos(int x)
{
return lower_bound(V.begin(), V.end(), x) - V.begin() + 1;
}
int root(int u)
{
return par[u] < 0 ? u : par[u] = root(par[u]);
}
void join(int u, int v)
{
if ((u = root(u)) == (v = root(v))) return;
if (par[u] > par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
}
int main()
{
if (fopen("tst.inp", "r"))
{
freopen("tst.inp", "r", stdin);
freopen("tst.out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i] >> b[i];
V.push_back(a[i]);
V.push_back(b[i]);
}
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
for (int i = 1; i <= V.size(); ++i) par[i] = - 1;
++out[V.size()];
++in[1];
join(1, V.size());
for (int i = 1; i <= n; ++i)
{
int x = pos(a[i]), y = pos(b[i]);
join(x, y);
++out[x];
++in[y];
}
vector <pair <int, pair <int, int> > > E;
int last = - 1;
long long ans = 0;
bool ok = 0;
for (int i = V.size(); i > 1; --i)
{
int diff = abs(out[i] - in[i]);
if (!diff)
{
ok = 1;
continue;
}
if (ok && last != - 1)
{
// cerr << V[last - 1] << ' ' << V[i - 1] << '\n';
E.push_back({V[last - 1] - V[i - 1], {last, i}});
// E.push_back({0, {i, last}});
}
ok = 0;
if (out[i] > in[i]) in[i] += diff, out[i - 1] += diff;
else out[i] += diff, in[i - 1] += diff, ans += 1LL * diff;
join(i, i - 1);
last = i - 1;
}
sort(E.begin(), E.end());
for (auto x: E)
{
int r1 = root(x.second.first);
int r2 = root(x.second.second);
if (r1 != r2) ans += 1LL * x.first, join(r1, r2);
}
cout << ans;
return 0;
}