제출 #1199728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199728		raphaelp	Roller Coaster Railroad (IOI16_railroad)	C++20	0 / 100	148 ms	23812 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({0, N});
    fin.push_back({1000000001, 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++)
        best += max(0, deb[i].first - fin[i].first);
    vector<vector<int>> cycles;
    for (int i = 0; i <= N; i++)
    {
        if (cycle[i] != -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();
    priority_queue<vector<int>> PQ;
    for (int i = 0; i < N; i++)
        PQ.push({-(max(0, deb[i + 1].first - fin[i].first) + max(0, deb[i].first - fin[i + 1].first) - max(0, deb[i + 1].first - fin[i + 1].first) - max(0, deb[i].first - fin[i].first)), i, i + 1, 0});
    vector<int> l(N + 2, N + 1), r(N + 2, N + 1), last(N + 2);
    for (int i = 0; i <= N; i++)
        l[i] = i - 1, r[i] = i + 1;
    l[0] = N + 1, r[N] = N + 1;
    int buff = 0;
    while (!PQ.empty())
    {
        int 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;
        if (last[x] > L || last[y] > L)
            continue;
        int c1 = cycle[deb[x].second], c2 = cycle[deb[y].second];
        if (cycles[c2].size() > cycles[c1].size())
            swap(c1, c2);
        for (int i = 0; i < cycles[c2].size(); i++)
        {
            cycles[c1].push_back(cycles[c2][i]);
            cycle[cycles[c2][i]] = c1;
        }
        cycles[c2].clear();
        nb--;
        last[x] = last[y] = ++buff;
        deb[y].first = deb[x].first;
        r[l[x]] = r[x];
        l[r[x]] = l[x];
        int a = l[x], b = r[x];
        if (a == N + 1 || b == N + 1)
            continue;
        PQ.push({-(max(0, deb[b].first - fin[a].first) + max(0, deb[a].first - fin[b].first) - max(0, deb[b].first - fin[b].first) - max(0, deb[a].first - fin[a].first)), a, b, buff});
    }
    return best;
}

컴파일 시 표준 에러 (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