Submission #74242

#	Time	Username	Problem	Language	Result	Execution time	Memory
74242		imeimi2000	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	293 ms	159844 KiB

railroad

#include "railroad.h"
#include <algorithm>
#include <functional>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

vector<int> cp;
vector<int> deg;
int compress(int x) {
    return lower_bound(cp.begin(), cp.end(), x) - cp.begin();
}

vector<int> par;
int find(int x) {
    if (par[x] != -1) return par[x] = find(par[x]);
    return x;
}

int merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return 0;
    par[y] = x;
    return 1;
}

llong plan_roller_coaster(vector<int> s, vector<int> t) {
    for (int i : s) cp.push_back(i);
    for (int i : t) cp.push_back(i);
    cp.push_back(0);
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    deg.resize(cp.size(), 0);
    par.resize(cp.size(), -1);
    for (int &i : s) i = compress(i);
    for (int &i : t) i = compress(i);
    
    for (int i : s) ++deg[i];
    for (int i : t) --deg[i];
    for (int i = 0; i < s.size(); ++i) merge(s[i], t[i]);
    
    llong ret = 0;
    for (int i = 1; i < cp.size(); ++i) {
        int ch = deg[i - 1] - (i == 1);
        if (ch != 0) merge(i - 1, i);
        deg[i - 1] -= ch;
        deg[i] += ch;
        if (ch > 0) ret += (llong)ch * (cp[i] - cp[i - 1]);
    }
    
    vector<pii> es;
    for (int i = 1; i < cp.size(); ++i) es.emplace_back(cp[i] - cp[i - 1], i);
    sort(es.begin(), es.end());
    for (pii _i : es) {
        int c, i;
        tie(c, i) = _i;
        if (merge(i - 1, i)) ret += c;
    }
    return ret;
}

Compilation message (stderr)

railroad.cpp: In function 'llong plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:42:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); ++i) merge(s[i], t[i]);
                     ~~^~~~~~~~~~
railroad.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < cp.size(); ++i) {
                     ~~^~~~~~~~~~~
railroad.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < cp.size(); ++i) es.emplace_back(cp[i] - cp[i - 1], i);
                     ~~^~~~~~~~~~~

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