Submission #240265

#	Time	Username	Problem	Language	Result	Execution time	Memory
240265		lyc	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	278 ms	18280 KiB

railroad

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

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

struct UnionFind {
    vector<int> p, sz;
    UnionFind(int n) { p.assign(n,0); iota(ALL(p),0); sz.assign(n,1); }
    int finds(int i) { return (p[i] == i) ? i : (p[i] = finds(p[i])); }
    bool unions(int i, int j) {
        int x = finds(i), y = finds(j);
        if (x != y) {
            if (sz[x] < sz[y]) swap(x,y);
            p[y] = x, sz[x] += sz[y];
            return true;
        } return false;
    }
};

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int N = SZ(s);
    vector<int> vals;
    for (int x : s) vals.push_back(x);
    for (int x : t) vals.push_back(x);
    sort(ALL(vals)); vals.resize(unique(ALL(vals))-vals.begin());
    int V = SZ(vals);
    int seg[V] = {0}; seg[0] = -1;
    UnionFind UF(V);
    FOR(i,0,N-1){
        s[i] = lower_bound(ALL(vals),s[i])-vals.begin();
        t[i] = lower_bound(ALL(vals),t[i])-vals.begin();
        if (s[i] <= t[i]) ++seg[s[i]], --seg[t[i]];
        else --seg[t[i]], ++seg[s[i]];
        UF.unions(s[i],t[i]);
    }
    long long ans = 0;
    vector<tuple<int,int,int>> el;
    FOR(i,0,V-2){
        if (i > 0) seg[i] += seg[i-1];
        if (seg[i] != 0) {
            ans += (long long) max(0,seg[i]) * (vals[i+1]-vals[i]);
            UF.unions(i,i+1);
        } else {
            el.emplace_back(vals[i+1]-vals[i],i,i+1);
        }
    }
    sort(ALL(el));
    for (auto& [w,u,v] : el) if (UF.unions(u,v)) { ans += w; }
    return ans;
}

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