백준 33768번: Ski Slope [C++]

작성일 | In
플래티넘 III 플래티넘 III

문제

Ski Slope

풀이

문제를 일반적인 형태로 바꾸어 봅시다.

문제에서 주어지는 waypoint끼리의 관계를 $1$이 루트인 트리로 나타낼 수 있습니다.

waypoint는 정점, ski run은 간선으로 생각합니다.

우리가 해결해야 하는 문제는 $1$에서 다른 정점까지의 경로 중 $s < d$인 간선을 최대 $c$개만 포함하는 경로의 $e$의 합의 최댓값을 구하는 것입니다.

$c = 0$

$c = 0$인 쿼리만 들어온다고 생각해 봅시다.

$D_i$를 정점 $i$에서 루트까지 $d$의 최댓값이라 합시다.

$c = 0$이므로 경로에서 어떤 간선도 $s$를 넘으면 안 됩니다.

따라서 $D_i$를 미리 정렬한 다음 이분 탐색을 통해서 $D_k \le s < D_{k + 1}$을 만족하는 $k$를 찾습니다. 이때 $D_i$는 정렬되었으므로 $k$는 정점 번호가 아님에 유의합시다.

이제 $i = 1$부터 $k$까지의 경우만 고려해주면 되고, 이는 전처리로 $O(N)$에 구해둘 수 있습니다.

$c \neq 0$

$c \neq 0$인 경우도 비슷하게 해결할 수 있습니다.

최대 $c$개의 간선은 $s$를 넘어도 상관없으므로 $c + 1$번째로 큰 간선의 가중치만 $s$를 넘지 않으면 됩니다.

$D_{ic}$를 정점 $i$에서 루트까지 $d$ 중 $c + 1$번째로 작은 값이라 정의합시다.

그렇다면 똑같이 $D_{ic}$를 미리 정렬한 다음 이분 탐색을 통해서 해결할 수 있습니다.

총 시간 복잡도는 $O(N + M\log N)$입니다.

코드

$E_i$를 루트에서 $i$번 정점까지 가는 경로의 $e$의 합으로 정의하고 $DE = (D_i, E_i)$ 순서쌍으로 관리했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
#define by_desc(x) [](const auto& a, const auto& b) { return a.x > b.x; }

using ll = long long;

template <typename T>
bool minimize(T& target, T value) {
    return target > value ? (target = value, true) : false;
}
template <typename T>
bool maximize(T& target, T value) {
    return target < value ? (target = value, true) : false;
}

constexpr int MX = 101010;

int p[MX], d[MX], e[MX];
pair<int, ll> DE[11][MX];
vector<int> top11[MX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 2; i <= N; i++)
        cin >> p[i] >> d[i] >> e[i];

    top11[1] = vector<int>(11);
    for (int i = 2; i <= N; i++) {
        top11[i] = top11[p[i]];
        top11[i].push_back(d[i]);
        sort(all(top11[i]), greater());
        top11[i].resize(11);
    }

    for (int c = 0; c <= 10; c++) {
        DE[c][1] = {top11[1][c], e[1]};

        for (int i = 2; i <= N; i++)
            DE[c][i] = {top11[i][c], DE[c][p[i]].second + e[i]};

        sort(DE[c] + 1, DE[c] + N + 1);
        for (int i = 2; i <= N; i++)
            maximize(DE[c][i].second, DE[c][i - 1].second);
    }

    int M;
    cin >> M;
    while (M--) {
        int s, c;
        cin >> s >> c;

        ll ans =
            (upper_bound(DE[c] + 1, DE[c] + N + 1, pair(s, 0), by(first)) - 1)
                ->second;

        cout << ans << "\n";
    }

    return 0;
}

백준 33768번: Ski Slope [C++]