| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 332088 | LifeHappen__ | Roller Coaster Railroad (IOI16_railroad) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
struct dsu {
vector <int> par;
int n;
dsu (int n) : n(n) {
par.assign(n, 0);
for (int i = 0; i < n; ++i) par[i] = i;
}
int findset(int u) {
if(par[u] == u) return u;
return par[u] = findset(par[u]);
}
bool mergeset(int u, int v) {
u = findset(u), v = findset(v);
if(u == v) return false;
par[v] = u; return true;
}
};
long long plan_roller_coaster(vector<int> s, vector<int> t) {
int n = s.size();
vector<int> vals;
for (int i = 0; i < n; ++i) {
vals.pb(s[i]); vals.pb(t[i]);
}
sort(begin(vals), end(vals));
vals.erase(unique(begin(vals), end(vals)));
dsu pa(vals.size() + 5);
vector<int> can(vals.size() + 5);
for (int i = 0; i < n; ++i) {
s[i] = lower_bound(begin(vals), end(vals), s[i]) - begin(vals);
t[i] = lower_bound(begin(vals), end(vals), t[i]) - begin(vals);
can[s[i]]++;
can[t[i]]--;
pa.mergeset(s[i], t[i]);
}
int m = vals.size();
int cur = 1;
int64_t ans = 0;
vector<tuple<int64_t, int, int>> ts;
for (int i = m - 1; i > 0; --i) {
cur += can[i];
if(cur < 0) {
ans += 1ll * (vals[i - 1] - vals[i]) * cur;
pa.mergeset(i - 1, i);
} else if(cur > 0) pa.mergeset(i - 1, i);
else ts.emplace_back(vals[i] - vals[i - 1], i, i - 1);
}
for (auto &_ : ts) {
int64_t w;
int u, v;
tie(w, u, v) = _;
if(pa.mergeset(u, v)) {
ans += w;
}
}
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("in.txt", "r", stdin);
int n; cin >> n;
vector <int> s(n), t(n);
for (int i = 0; i < n; ++i) {
cin >> s[i] >> t[i];
}
cout << plan_roller_coaster(s, t);
}