DMOPC '21 Contest 1 P4 - Uneven Forest

View as PDF

Submit solution

Points: 20
Time limit: 4.0s
Memory limit: 256M

Problem type

As a realist hero, you know that forests should be as even as possible, or some trees may grow too large and hog all of the sunlight. Specifically, the unevenness of a forest is the length of the longest simple path in that forest. The forest you are to manage consists of N nodes and M edges, where the i-th edge connects nodes u_i and v_i with a length of l_i and a beauty of b_i. You may remove some set of edges in the forest with your magical saw, but the sum of the beauty of the edges removed must not exceed K. Given these conditions, what is the minimum possible unevenness of the resulting forest?


1 \le M < N \le 10^3

1 \le u_i, v_i \le N

1 \le l_i, b_i, K \le 10^9

The edges form a forest (i.e., an acyclic undirected graph).

Input Specification

The first line contains 3 integers N, M, and K.

The next M lines each contain 4 integers u_i, v_i, l_i, and b_i.

Output Specification

Output a single integer, representing the minimum possible unevenness of the resulting forest.

Sample Input

10 7 6
1 3 2 1
3 2 1 3
3 4 2 5
5 4 3 2
7 6 2 4
4 6 4 3
9 10 3 2

Sample Output



For example, one solution is to remove the first, fourth, and sixth edges, giving an unevenness of 3.


There are no comments at the moment.