Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "railroad.h"
- #include <vector>
- #include <algorithm>
- #include <cstdio>
- #include <cstring>
- #include <map>
- #include <unordered_map>
- #define X first
- #define Y second
- #define PB push_back
- using namespace std;
- typedef vector < int > vi;
- typedef long long ll;
- typedef pair < int , int > pii;
- typedef vector < pii > vp;
- const int INF = 0x3f3f3f3f;
- const int N = 4e5 + 500;
- bool cmp(pii A, pii B){
- if(A.X - A.Y == B.X - B.Y) return A.X < A.Y;
- return A.X - A.Y > B.X - B.Y;
- }
- int n, m;
- vector < int > v;
- vector < pii > e;
- unordered_map < int , int > deg, par, out;
- int pr(int x){
- if(!par[x]) return par[x] = x;
- if(x == par[x]) return x;
- return par[x] = pr(par[x]);
- }
- void mrg(int x,int y){
- par[pr(x)] = pr(y);
- }
- ll plan_roller_coaster(vi s, vi t) {
- n = s.size();
- for(int i = 0;i < n;i++){
- deg[s[i]]++; deg[t[i]]--;
- v.PB(s[i]), v.PB(t[i]);
- mrg(s[i], t[i]);
- }
- sort(v.begin(), v.end());
- v.erase(unique(v.begin(), v.end()), v.end());
- n = (int)v.size();
- ll sol = 0;
- for(int i = 0;i < n;i++){
- out[v[i]] = out[v[i - 1]] - deg[v[i]] + (i == 0) - (i == n - 1);
- if(out[v[i]] < 0 && i != n - 1){
- mrg(v[i], v[i + 1]);
- sol -= (ll)(v[i + 1] - v[i]) * out[v[i]];
- }
- if(out[v[i]] == 0 && i != n - 1){
- e.PB({v[i], v[i + 1]});
- }
- if(out[v[i]] > 0 && i != n - 1){
- mrg(v[i], v[i + 1]);
- }
- //printf("OUT %d je %d\n:", v[i], out[v[i]]);
- }
- //printf("SOL = %lld\n", sol);
- sort(e.begin(), e.end(), cmp);
- for(int i = 0;i < e.size();i++){
- if(pr(e[i].X) != pr(e[i].Y)){
- mrg(e[i].X, e[i].Y);
- sol += e[i].Y - e[i].X;
- }
- }
- return sol;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement