Submission #622877

#	Time	Username	Problem	Language	Result	Execution time	Memory
622877		leaked	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	878 ms	63328 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"

#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define m_p make_pair
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}



const int N=4e5+4;

int p[N];
void make(int v){
    p[v]=v;
}
int get(int v){
    return p[v]=(p[v]==v?v:get(p[v]));
}
int mg(int a,int b){
    a=get(a),b=get(b);
    if(a==b) return 0;
    p[a]=b;
    return 1;
}

ll plan_roller_coaster(std::vector<int> s, std::vector<int> t){
//    assert(false);
    vec<int> x;
//    s.pb(1e9);t.pb(1);
    map<int,int> mp;
    map<int,int> cons;
    map<int,int> id;
    int tt=0;
    for(int i=0;i<sz(s);i++){
//        cout<<s[i]<<' '<<t[i]<<endl;
        mp[s[i]]++;mp[t[i]]--;
    }
    int bl=0,jt=0;
    vec<pii> xs;
    ll ans=0;

    mp[0]--;
    for(auto &z : mp){
//        cout<<z.f<<' '<<z.s<<endl;
        bl+=z.s;
        id[z.f]=tt++;
        ///from
        xs.pb({z.f,bl});
    }

    vec<int> vc;

    for(int i=0;i<sz(xs);i++) make(i);


    for(int i=0;i+1<sz(xs);i++){
//        cout<<xs[i].f<<' '<<xs[i].s<<endl;
        if(xs[i].s>0) ans+=1ll*(xs[i+1].f-xs[i].f)*xs[i].s,mg(i,i+1);
        else if(xs[i].s<0) mg(i,i+1);
    }


    vec<array<int,3>> arr;
    for(int i=0;i<sz(s);i++) mg(id[s[i]],id[t[i]]);

    for(int i=0;i+1<sz(xs);i++){
        arr.pb({xs[i+1].f-xs[i].f,i,i+1});
    }
    sort(all(arr));
    for(auto &z : arr){
        if(mg(z[1],z[2]))
            ans+=z[0];
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:51:14: warning: unused variable 'jt' [-Wunused-variable]
   51 |     int bl=0,jt=0;
      |              ^~

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36