Submission #293301

#	Time	Username	Problem	Language	Result	Execution time	Memory
293301		peti1234	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	209 ms	21356 KiB

railroad

#include <bits/stdc++.h>

using namespace std;
const int c=200003;
long long n, sum, si, dbe, dki, hv[c], o=0;
vector<pair<int, int> >sz;
vector<pair<int, pair<int, int> > > el;
int holvan(int a) {
    if (!hv[a]) return a;
    int x=holvan(hv[a]);
    hv[a]=x;
    return x;
}
void unio(int a, int b) {
    a=holvan(a), b=holvan(b);
    if (a!=b) hv[a]=b;
}
long long plan_roller_coaster(vector<int> b, vector<int> a) {
    n=a.size();
    for (int i=0; i<n; i++) {
        sz.push_back({a[i], -(i+1)});
        sz.push_back({b[i], i+1});
    }
    n++, dki++;
    sz.push_back({1e9, n}), sz.push_back({1, -n});
    si=sz.size();
    sort(sz.begin(), sz.end());
    for (int i=1; i<si; i++) {
        long long bal=dbe-dki, id=sz[i].second, pr=sz[i-1].second, kul=sz[i].first-sz[i-1].first;
        if (bal!=0) {
            sum+=max(o, bal*kul);
            unio(abs(id), abs(pr));
        }
        el.push_back({kul, {abs(id), abs(pr)}});
        if (id>0) dbe++;
        else dki++;
    }
    sort(el.begin(), el.end());
    for (int i=0; i<el.size(); i++) {
        int d=el[i].first, x=el[i].second.first, y=el[i].second.second;
        if (holvan(x)!=holvan(y)) sum+=d, unio(x, y);
    }
    return sum;
}

Compilation message (stderr)

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

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