Submission #1312054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312054		settop	Roller Coaster Railroad (IOI16_railroad)	C++20	30 / 100	292 ms	28596 KiB

railroad

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

using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
const ll inf=1e16;
typedef pair<ll,ll> pii;

vector<int> pai;
vector<int> out,in;

int find(int x){
    return x==pai[x]?x:pai[x]=find(pai[x]);
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = sz(s);

    pai.resize(n);
    out.resize(n);
    in.resize(n);

    vector<bool> z(n);

    fall(i,0,n-1) pai[i]=i;

    set<pii> st;

    fall(i,0,n-1) st.insert({s[i],i});

    vector<int> ord;

    fall(i,0,n-1) ord.pb(i);

    sort(all(ord),[&](int a,int b){
        if(t[a]!=t[b]) return t[a]>t[b];
        return a<b;
    });

    ll ans=inf;

    for(auto u:ord){
        auto it=st.lower_bound({t[u],-1});
        if(it==st.end()){
            z[u]=1;
            continue;
        
        }
                
        auto [x,i]=*it; 
        if(find(i)!=find(u)){
            pai[find(i)]=find(u);
            st.erase(it);
            continue;
        }
        it++;
        if(it==st.end()){
            z[u]=1;
            continue;
        }
        
        pai[find((*it).second)]=find(u);
        st.erase(it);    
    }

    if(sz(st)==1) return 0;

    multiset<ll> st2;

    ll soma=0;

    fall(i,0,n-1) if(z[i]) out[find(i)]=t[i],st2.insert(t[i]),soma+=t[i];

    for(auto [u,j]:st){
        in[find(j)]=u;
        soma-=u;
    }
    
    fall(i,0,n-1){
        if(find(i)!=i) continue;
        ll cur=soma+s[i];
        st2.erase(st2.find(out[i]));
        cur-=*st2.rbegin();
        ans=min(ans,cur);
        st2.insert(out[i]);
    }

    return ans;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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