Submission #588235

#	Time	Username	Problem	Language	Result	Execution time	Memory
588235		SlavicG	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	181 ms	11560 KiB

railroad

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

using namespace std;

const int N = 4e5 + 10;
int p[N], balance[N];
int get(int a) {
    return p[a] = (p[a] == a ? a : get(p[a]));
}
int uni(int a, int b) {
    a = get(a), b = get(b);
    if(a == b) return 0;
    p[a] = b;
    return 1;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    for(int i = 0; i < N; ++i) p[i] = i;
    s.push_back((int)1e9);
    t.push_back(1);
    vector<int> c;
    for(int i = 0; i < s.size(); ++i) c.push_back(s[i]), c.push_back(t[i]);
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    for(int i = 0; i < (int)s.size(); ++i) {
        s[i] = lower_bound(c.begin(), c.end(), s[i]) - c.begin();
        t[i] = lower_bound(c.begin(), c.end(), t[i]) - c.begin();

        ++balance[s[i]], --balance[t[i]];
        uni(s[i], t[i]);
    }

    long long ans = 0;
    vector<pair<int, int>> edges;

    for(int i = 0; i + 1 < (int)c.size(); ++i) {
        balance[i + 1] += balance[i];
        ans += 1LL * (c[i + 1] - c[i]) * max(0, balance[i]);

        if(balance[i] == 0) edges.push_back({c[i + 1] - c[i], i});
        else uni(i, i + 1);
    }

    sort(edges.begin(), edges.end());
    for(auto [c, i] : edges) {
        if(uni(i, i + 1)) {
            ans += c;
        }
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0; i < s.size(); ++i) c.push_back(s[i]), c.push_back(t[i]);
      |                    ~~^~~~~~~~~~

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