Mreža
레이팅 미적용의견: 0
The city mayor Mirko lives in a city with \(n\) neighborhoods connected with \(n - 1\)
bidirectional roads such that from any neighborhood it is possible to reach every
other neighborhood.
Mirko wants to upgrade some roads to reduce traffic. For every road, we know the
current speed \(v@@RISE_MATH_BLOCK_0@@i\) and the speed of
driving after upgrading \(s@@RISE_MATH_BLOCK_1@@i\) euros in upgrading
roads between neighborhoods \(a_{i}\) and \(b_{i}\)”
For each suggestion, Mirko is interested in what is the minimum driving speed between neighborhoods
\(a@@RISE_MATH_BLOCK_2@@i\) if he spends at most \(e\)\(i\) euros on upgrading the roads, given thathis goal is to maximize the
minimum driving speed between the neighborhoods \(a_{i}\) and \(b_{i}\).
Mirko soon realized that calculating this is not an easy task and hired you to help him!
Subtask 1 (21 points): n, \(q \le 1\,000\)
Subtask 2 (29 points): Each of the neighborhoods will be connected with at most 2 other neighborhoods.
Subtask 3 (60 points): No additional constraints.
The first line contains the integer \(n\) (\(2 \le n \le 100\), 000), the number of neighborhoods.
In each of the next \(n - 1\) lines there are five integers \(x@@RISE_MATH_BLOCK_0@@i\), \(v@@RISE_MATH_BLOCK_1@@i\), \(s@@RISE_MATH_BLOCK_2@@i\), y\(i \le n\), \(1 \le v@@RISE_MATH_BLOCK_3@@i\) ≤
\(10^{9}\), \(1 \le c@@RISE_MATH_BLOCK_4@@i\) and \(y@@RISE_MATH_BLOCK_5@@i\), cost
of upgrading the road is \(c_{i}\), and the speed on the road would be \(s_{i}\).
The next line contains the integer \(q\) (\(1 \le q \le 100\,000\)), the number of unsatisfied citizens.
In each of the next \(q\) lines there are three integers \(a@@RISE_MATH_BLOCK_6@@i\), \(e@@RISE_MATH_BLOCK_7@@i\), b\(i \le n\), a\(i\)̸ = \(b@@RISE_MATH_BLOCK_8@@i \le 10^{18}\)), which
describe the suggestion of the \(i-th\) citizen.
In the \(i-th\) of the \(q\) lines print the answer to the request of the \(i-th\) citizen.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 21점 | n, \(q \le 1\,000\) |
2 | 29점 | Each of the neighborhoods will be connected with at most 2 other neighborhoods. |
3 | 60점 | No additional constraints. |
6
1 2 5 7 10
1 3 4 8 9
3 4 7 1 15
3 5 6 3 11
3 6 5 6 8
3
2 4 15
6 4 5
3 5 107
5
114
1 2 5 5 8
2 3 4 6 9
3 4 6 10 7
4
1 4 16
2 4 16
1 4 10
3 4 106
7
5
7Clarification of the first example:
The illustration represents the city and its neighborhoods. On the edges are written the current driving
speed, the cost of upgrading, and the speed after upgrading, respectively.
If we upgrade the roads between 1 and 2, and between 1 and 3, the driving speeds from 2 to 4 will be 10,
9, and 7 m/s. The minimum is 7 m/s.
If we upgrade the roads between 4 and 3, the driving speeds from 6 to 4 will be 5 an 15 m/s. The
minimum is 5 m/s.
If we upgrade the road between 3 and 5, the driving speed from 5 to 3 will be 11 m/s.
평가 및 의견
Mreža
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Mreža