Submission #1199702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199702		raphaelp	Roller Coaster Railroad (IOI16_railroad)	C++20	0 / 100	69 ms	9812 KiB

railroad

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

long long plan_roller_coaster(vector<int> s, vector<int> t)
{
    int N = (int)s.size();
    vector<pair<int, int>> deb, fin;
    for (int i = 0; i < N; i++)
        deb.push_back({t[i], i}), fin.push_back({s[i], i});
    deb.push_back({1, N});
    fin.push_back({1000000000, N});
    sort(deb.begin(), deb.end());
    sort(fin.begin(), fin.end());
    long long best = 0;
    vector<int> cycle(N + 1, -1), inv(N + 1);
    for (int i = 0; i <= N; i++)
        inv[deb[i].second] = i;
    for (int i = 0; i <= N; i++)
        if (fin[i].first < deb[i].first)
            return 1;
    vector<vector<int>> cycles;
    for (int i = 0; i <= N; i++)
    {
        if (cycle[N] != -1)
            continue;
        cycles.push_back({});
        int 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];
        }
    }
    int nb = cycles.size();
    int R = 0, c = 0;
    for (int i = 0; i <= N; i++)
    {
        if (deb[i].first <= R && cycle[deb[i].second] != c)
        {
            int c2 = cycle[deb[i].second];
            if (cycles[c2].size() > cycles[c].size())
                swap(c, c2);
            for (int j = 0; j < cycles[c2].size(); j++)
            {
                cycles[c].push_back(cycles[c2][j]);
                cycle[cycles[c2][j]] = c;
            }
            cycles[c2].clear();
            nb--;
        }
        R = fin[i].first;
        c = cycle[deb[i].second];
    }
    if (nb == 1)
        return 0;
    return 1;
}

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: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36