Submission #578636

#	Time	Username	Problem	Language	Result	Execution time	Memory
578636		jasmin	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	810 ms	42648 KiB

railroad

#include<bits/stdc++.h>
#include "railroad.h"
using namespace std;
#define int long long

const int inf=1e18;

struct graph{
    vector<pair<int, pair<int,int> > >e;
    unordered_map<int, int> chef;

    int find(int v){
        if(chef[v]==0 || chef[v]==v){
            return chef[v]=v;
        }
        return chef[v]=find(chef[v]);
    }
    bool unite(int a, int b){
        if(find(a)==find(b)) return false;
        chef[find(a)]=find(b);
        return true;
    }

    int mst(){
        int ans=0;
        sort(e.begin(), e.end());

        for(auto edge: e){
            if(unite(edge.second.first, edge.second.second)){
                ans+=edge.first;
            }
        }
        return ans;
    }
};

int plan_roller_coaster(vector<int32_t> s, vector<int32_t> t){
    int n=s.size();
    
    graph g;
    vector<pair<int, int> > time;
    for(int i=0; i<n; i++){
        time.push_back({s[i], 1});
        time.push_back({t[i], -1});
        g.unite(s[i], t[i]);
    }
    sort(time.begin(), time.end());

    int sum=-1;
    int ans=0;
    for(int i=0; i<(int)time.size()-1; i++){

        sum+=time[i].second;
        ans+=max((int)0, (time[i+1].first-time[i].first)*sum);
        
        if(sum==0){
            g.e.push_back({time[i+1].first-time[i].first, {time[i+1].first, time[i].first}});
        }
        else{
            g.unite(time[i+1].first, time[i].first);
        }
    }

    ans+=g.mst();
    return ans;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int32_t> s(n);
    vector<int32_t> t(n);
    for(int i=0; i<n; i++){
        cin >> s[i];
    }
    for(int i=0; i<n; i++){
        cin >> t[i];
    }
    cout << plan_roller_coaster(s, t) << "\n";
}*/

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