Submission #622864

#	Time	Username	Problem	Language	Result	Execution time	Memory
622864		leaked	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	1155 ms	68480 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;
        if(s[i]<t[i]) mp[s[i]]++,mp[t[i]]--,cons[s[i]]++,cons[t[i]]--;
        else mp[t[i]]--,mp[s[i]]++,cons[t[i]]++,cons[s[i]]--;
    }
    int bl=0,jt=0;
    vec<pii> xs;
    ll ans=0;
    for(auto &z : mp){
//        cout<<z.f<<' '<<z.s<<endl;
        bl+=z.s;jt+=cons[z.f];
        cons[z.f]=jt;id[z.f]=tt++;
        ///from
        xs.pb({z.f,bl});
    }

    vec<int> vc;

    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,xs[i].s=0,cons[xs[i].f]++;
    }

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

    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+2<sz(xs);i++){
        if(cons[xs[i].f]) mg(i,i+1);
        else 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;
}

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