Submission #1283629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283629		Johann	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	100 ms	23544 KiB

railroad

#include "railroad.h"

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

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<vi> vvi;
typedef tuple<int, int, int> tiii;
typedef vector<tiii> vtiii;

#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)

struct unionfind
{
    vi arr;
    void init(int size)
    {
        arr.resize(size);
        iota(all(arr), 0);
    }
    int find(int a)
    {
        return arr[a] = (arr[a] == a) ? a : find(arr[a]);
    }
    void merge(int a, int b)
    {
        a = find(a);
        b = find(b);
        arr[b] = a;
    }
};

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
    int n = (int)s.size();
    int maxi = *max_element(all(t));
    s.push_back(maxi), t.push_back(1);
    ++n;

    vpii L(n), R(n);
    for (int i = 0; i < n; ++i)
        L[i] = make_pair(t[i], i),
        R[i] = make_pair(s[i], i);
    sort(all(L)), sort(all(R));
    vi tmp_back_edges(n);
    for (int i = 0; i < n; ++i)
        tmp_back_edges[L[i].second] = i;
    vi back_edges(n);
    for (int i = 0; i < n; ++i)
        back_edges[i] = tmp_back_edges[R[i].second];

    ll ans = 0;
    unionfind uf;
    uf.init(n);
    auto comp_cost = [L, R](int l, int r)
    { return max(0LL, L[l].first - R[r].first); };
    for (int v = 0; v < n; ++v)
    {
        ans += comp_cost(v, v); // arrow from L[i] -> R[i] which in general are different pieces
        uf.merge(v, back_edges[v]);
    }

    vpii options;
    // {c, i} := c is the cost saving of letting the arrow pointing to R[i] point to R[i + 1] and the arrow pointing to R[i+1] point to R[i]
    // only do this operation if it merges components
    for (int i = 0; i < n - 1; ++i)
    {
        ll c = (comp_cost(i + 1, i) + comp_cost(i, i + 1)) - (comp_cost(i, i) + comp_cost(i + 1, i + 1));
        options.push_back(make_pair(c, i));
    }
    sort(all(options));
    for (pii foo : options)
    {
        ll c, i;
        tie(c, i) = foo;
        if (uf.find(i) != uf.find(i + 1))
        {
            uf.merge(i, i + 1);
            ans += c;
        }
    }

    return ans;
}

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