Ski Slope
실버 II의견: 0
Bessie is going on a ski trip with her friends. The mountain has \(N\) waypoints
(\(1\leq N \leq 10^5\)) labeled \(1, 2, \ldots, N\) in increasing order of altitude
(waypoint \(1\) is the bottom of the mountain).
For each waypoint \(i > 1\), there is a ski run starting from waypoint \(i\) and
ending at waypoint \(p_i\) (\(1\le p_i
(\(0 \leq d_i \leq 10^9\)) and enjoyment \(e_i\) (\(0 \leq e_i \leq 10^9\)).
Each of Bessie's \(M\) friends (\(1\leq M \leq 10^5\)) will do the following: They
will pick some initial waypoint \(i\) to start at, and then follow the runs
downward (to \(p_i\), then to \(p_{p_i}\), and so forth) until they get to waypoint
\(1\).
The enjoyment each friend gets is equal to the sum of the enjoyments of the runs
they follow. Each friend also has a different skill level \(s_j\)
(\(0 \leq s_j \leq 10^9\)) and courage level \(c_j\) (\(0 \leq c_j \leq 10\)), which
limits them to selecting an initial waypoint that results in them taking at
most \(c_j\) runs with difficulty greater than \(s_j\).
For each friend, compute the maximum enjoyment they can get.
Problem credits: Brandon Wang
SCORING
- Inputs 2-4: \(N, M\le 1000\)
- Inputs 5-7: All \(c_j=0\)
- Inputs 8-17: No additional constraints.
Problem credits: Brandon Wang
The first line contains \(N\).
Then for each \(i\) from \(2\) to \(N\), a line follows containing three
space-separated integers \(p_i\), \(d_i\), and \(e_i\).
The next line contains \(M\).
The next \(M\) lines each contain two space-separated integers \(s_j\) and \(c_j\).
Output \(M\) lines, with the answer for each friend on a separate line.
Note that the large size of integers involved in this problem may require the
use of 64-bit integer data types (e.g., a "long long" in C/C++).
4
1 20 200
2 30 300
2 10 100
8
19 0
19 1
19 2
20 0
20 1
20 2
29 0
30 00
300
500
300
500
500
300
500- The first friend cannot start any waypoint other than \(1\), since any other waypoint would cause them to take at least one run with difficulty greater than \(19\). Their total enjoyment is \(0\).
- The second friend can start at waypoint \(4\) and take runs down to waypoint \(2\) and then \(1\). Their total enjoyment is \(100+200=300\). They take one run with difficulty greater than \(19\).
- The third friend can start at waypoint \(3\) and take runs down to waypoint \(2\) and then \(1\). Their total enjoyment is \(300+200=500\). They take two runs with difficulty greater than \(19\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > US Open > Silver
평가 및 의견
Ski Slope
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Ski Slope