Submission #210625

#	Time	Username	Problem	Language	Result	Execution time	Memory
210625		anonymous	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	628 ms	42904 KiB

railroad

#include "railroad.h"
#include <map>
#include <set>
#include <utility>
#include <vector>
#include <algorithm>
#include <cassert>
#define MAXN 200005
#define LL long long
using namespace std;
class DSU {
    int Set[MAXN];
public:
    void init(int n) {for(int i=0; i<=n; i++) {Set[i]=i;};}
    int Find(int x) {return(Set[x] == x ? x : Set[x] = Find(Set[x]));}
    void Union(int x, int y) {Set[Find(x)] = Find(y);}
} UF;

multiset<pair<pair<int,int> , bool> > R; // [[val, id], s = true, t = false]
bool active[MAXN];
LL plan_roller_coaster(vector<int> s, vector<int> t) {
    int N = (int) s.size();
    LL ans = 0;
    UF.init(N);
    for (int i=0; i < N; i++) {
        R.insert({{s[i],i}, true});
        R.insert({{t[i],i}, false});
    }
    R.insert({{0, N}, false});
    R.insert({{1<<30, N}, true});
    int up=0, down=0;
    for (auto p: R) {
        if (!active[p.first.second]) {
            if (p.second) {up++;}
            else {down++;}
            active[p.first.second] = true;
        } else {
            if (p.second) {down--;}
            else {up--;}
            active[p.first.second] = false;
        }
        if (down > up && p != *R.rbegin()) {
            //printf("Link up %d %d\n", p.first.first,(*R.upper_bound(p)).first.first);
            UF.Union(p.first.second, (*R.upper_bound(p)).first.second);
        } else if (up > down) {
            assert(p != *R.rbegin());
            //printf("Link down %d %d\n", p.first.first,(*R.upper_bound(p)).first.first);
            ans += ((LL) (*R.upper_bound(p)).first.first - p.first.first)*((LL) up - down);
            UF.Union(p.first.second, (*R.upper_bound(p)).first.second);
        }
    }
    //printf("%d\n", ans);
    vector<pair<int, pair<int,int> > > Edge;
    int prev_id, prev_pos;
    for (auto p: R) {
        if (p == *R.begin()) {
            prev_id = p.first.second, prev_pos = p.first.first;
            continue;
        } else {
            Edge.push_back({p.first.first - prev_pos, {p.first.second, prev_id}});
            prev_id = p.first.second, prev_pos = p.first.first;
        }
    }
    sort(Edge.begin(), Edge.end());
    for (auto e: Edge) {
        if (UF.Find(e.second.first) != UF.Find(e.second.second)) {
            UF.Union(e.second.first, e.second.second);
            ans += e.first;
        }
    }
    return(ans);
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:60:43: warning: 'prev_pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
             Edge.push_back({p.first.first - prev_pos, {p.first.second, prev_id}});
                             ~~~~~~~~~~~~~~^~~~~~~~~~

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