Submission #698499

#	Time	Username	Problem	Language	Result	Execution time	Memory
698499		qwerasdfzxcl	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	174 ms	15084 KiB

railroad

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

using namespace std;
typedef long long ll;
struct DSU{
    int path[400400];
    void init(int n){for (int i=0;i<=n;i++) path[i] = i;}
    int find(int s){
        if (s==path[s]) return s;
        return path[s] = find(path[s]);
    }
    bool merge(int s, int v){
        s = find(s), v = find(v);
        if (s==v) return 0;
        path[s] = v;
        return 1;
    }
}dsu;
int n, deg[400400];
vector<int> a;

long long plan_roller_coaster(std::vector<int> S, std::vector<int> T) {
    n = S.size();
    a.push_back(1);
    a.push_back(1e9+100);

    for (int i=0;i<n;i++) {a.push_back(S[i]); a.push_back(T[i]);}
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    dsu.init(a.size());

    for (int i=0;i<n;i++){
        int x = lower_bound(a.begin(), a.end(), S[i]) - a.begin();
        int y = lower_bound(a.begin(), a.end(), T[i]) - a.begin();

        deg[x]++;
        deg[y]--;
        dsu.merge(x, y);
    }

    ll ans = 0;
    for (int i=0;i<(int)a.size()-1;i++){
        //printf("%d -> %d\n", a[i], deg[i]);

        int target = i?0:1;
        if (deg[i]!=target) dsu.merge(i, i+1);

        ans += (deg[i] > target)?((ll)(deg[i]-target)*(a[i+1] - a[i])):0LL;
        deg[i+1] += deg[i] - target;
        deg[i] -= deg[i] - target;
    }

    vector<pair<int, int>> E;
    for (int i=0;i<(int)a.size()-1;i++) if (dsu.find(i) != dsu.find(i+1)){
        E.emplace_back(a[i+1] - a[i], i);
    }

    sort(E.begin(), E.end());
    for (auto &[x, y]:E) if (dsu.merge(y, y+1)) ans += x;

    return ans;
}

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