Submission #54322

#	Time	Username	Problem	Language	Result	Execution time	Memory
54322		Alexa2001	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	1419 ms	181952 KiB

railroad

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

using namespace std;

typedef long long ll;
typedef pair<int,int> Pair;
const int Nmax = 4e5 + 5, lim = 1e9;

int n, len[Nmax], t[Nmax], comp[Nmax], balance[Nmax];
map<int, int> mp;
vector<int> v[Nmax];
vector< pair<int, Pair> > edge;

void dfs(int node, int c)
{
    comp[node] = c;
    for(auto it : v[node])
        if(!comp[it]) dfs(it, c);
}

void add_edge_for_apm(int x, int y, int cost)
{
    edge.push_back({ cost, {x, y} });
}

void add_edge(int x, int y)
{
    v[x].push_back(y);
    v[y].push_back(x);
}

int boss(int x)
{
    if(x == t[x]) return x;
    return t[x] = boss(t[x]);
}

void unite(int x, int y)
{
    t[t[x]] = t[y];
}

void APM(ll &ans, int n)
{
    int i;
    for(i=1; i<=n; ++i) t[i] = i;

    sort(edge.begin(), edge.end());
    int x, y, cost;
    for(auto it : edge)
    {
        x = it.second.first;
        y = it.second.second;
        cost = it.first;

        if(boss(x) == boss(y)) continue;
        ans += cost;
        unite(x, y);
    }
}

ll plan_roller_coaster(vector<int> s, vector<int> t)
{
    s.push_back(lim);
    t.push_back(1);

    for(auto it : s) mp[it] ++;
    for(auto it : t) mp[it] --;

    int n = 0, sum = 0, prv = 0;
    for(auto &it : mp)
    {
        sum += it.second;
        len[n] = it.first - prv;
        balance[++n] = sum;

        it.second = n;
        prv = it.first;
    }

    ll ans = 0;
    int i;

    for(i=1; i<n; ++i)
        if(balance[i])
        {
            ans += (ll) len[i] * max(0, balance[i]);
            add_edge(i, i+1);
        }

    for(i=0; i<s.size(); ++i)
        add_edge(mp[s[i]], mp[t[i]]);

    int Comp = 0;
    for(i=1; i<=n; ++i)
        if(!comp[i])
            dfs(i, ++Comp);

    for(i=1; i<n; ++i)
        add_edge_for_apm(comp[i], comp[i+1], len[i]);

    APM(ans, Comp);
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<s.size(); ++i)
              ~^~~~~~~~~

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