Submission #1199743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199743		raphaelp	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	388 ms	56156 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;

long long plan_roller_coaster(vector<int> s, vector<int> t)
{
    long long N = (long long)s.size();
    vector<pair<long long, long long>> deb, fin;
    for (long long i = 0; i < N; i++)
        deb.push_back({t[i], i}), fin.push_back({s[i], i});
    deb.push_back({0, N});
    fin.push_back({1000000001, N});
    sort(deb.begin(), deb.end());
    sort(fin.begin(), fin.end());
    long long best = 0;
    vector<long long> cycle(N + 1, -1), inv(N + 1);
    for (long long i = 0; i <= N; i++)
        inv[deb[i].second] = i;
    for (long long i = 0; i <= N; i++)
        best += max(0LL, deb[i].first - fin[i].first);
    vector<vector<long long>> cycles;
    for (long long i = 0; i <= N; i++)
    {
        if (cycle[i] != -1)
            continue;
        cycles.push_back({});
        long long x = inv[i];
        while (cycle[deb[x].second] == -1)
        {
            cycle[deb[x].second] = cycles.size() - 1;
            cycles.back().push_back(deb[x].second);
            x = inv[fin[x].second];
        }
    }
    long long nb = cycles.size();
    priority_queue<vector<long long>> PQ;
    for (long long i = 0; i < N; i++)
        PQ.push({-(max(0LL, deb[i + 1].first - fin[i].first) + max(0LL, deb[i].first - fin[i + 1].first) - max(0LL, deb[i + 1].first - fin[i + 1].first) - max(0LL, deb[i].first - fin[i].first)), i, i + 1, 0});
    vector<long long> l(N + 2, N + 1), r(N + 2, N + 1), last(N + 2);
    for (long long i = 0; i <= N; i++)
        l[i] = i - 1, r[i] = i + 1;
    l[0] = N + 1, r[N] = N + 1;
    long long buff = 0;
    while (!PQ.empty())
    {
        long long cost = -PQ.top()[0], x = PQ.top()[1], y = PQ.top()[2], L = PQ.top()[3];
        PQ.pop();
        if (cycle[deb[x].second] == cycle[deb[y].second])
            continue;

        best += cost;
        long long c1 = cycle[deb[x].second], c2 = cycle[deb[y].second];
        if (cycles[c2].size() > cycles[c1].size())
            swap(c1, c2);
        for (long long i = 0; i < cycles[c2].size(); i++)
        {
            cycles[c1].push_back(cycles[c2][i]);
            cycle[cycles[c2][i]] = c1;
        }
        last[x] = last[y] = ++buff;
        deb[y].first = deb[x].first;
        r[l[x]] = r[x];
        l[r[x]] = l[x];
    }
    return best;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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