Submission #603262

#	Time	Username	Problem	Language	Result	Execution time	Memory
603262		georgievskiy	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	188 ms	15732 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct DSU {
    vector<int> p;
    DSU(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }
    int get(int x) {
        return p[x] = (x == p[x] ? x : get(p[x]));
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return 0;
        p[x] = y;
        return 1;
    }
    void print() {
        for (int i = 0; i < p.size(); i++) cout << get(i) << " "; cout << "\n";
    }
};

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    vector<int> a;
    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());
    for (int i = 0; i < n; i++)
        s[i] = lower_bound(a.begin(), a.end(), s[i]) - a.begin(),
        t[i] = lower_bound(a.begin(), a.end(), t[i]) - a.begin();
    int m = a.size();
    a.push_back(2e9);
    vector<int> cs(m), ct(m);
    DSU dsu(m);
    for (int i = 0; i < n; i++)
        cs[s[i]]++, ct[t[i]]++;
    for (int i = 0; i < n; i++)
        dsu.unite(s[i], t[i]);

    int cur = -1;
    ll ans = 0;
    vector<pii> w;
    for (int i = 0; i < m; i++) {
        cur += cs[i] - ct[i];
        if (cur > 0) {
            ans += 1ll * cur * (a[i + 1] - a[i]);
            //cur = 0;
            dsu.unite(i, i + 1);
        }
        if (i == m - 1) continue;
        if (cur < 0) dsu.unite(i, i + 1);
        if (cur == 0) w.push_back({a[i + 1] - a[i], i});
    }
    //dsu.print();
    sort(w.begin(), w.end());
    for (auto e : w) {
        int u = e.second, v = e.second + 1;
        if (dsu.unite(u, v)) ans += e.first;
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In member function 'void DSU::print()':
railroad.cpp:23:27: 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 < p.size(); i++) cout << get(i) << " "; cout << "\n";
      |                         ~~^~~~~~~~~~
railroad.cpp:23:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 |         for (int i = 0; i < p.size(); i++) cout << get(i) << " "; cout << "\n";
      |         ^~~
railroad.cpp:23:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |         for (int i = 0; i < p.size(); i++) cout << get(i) << " "; cout << "\n";
      |                                                                   ^~~~

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