2756 - Gifts for Jerry 2756 - Gifts for Jerry 2756 - Gifts for Jerry

Statistics Sub: 285 | AC: 45 | AC%: 15,79 | Score: 2,82
Created by José Carlos González Fernández
Added by jcfernandez (2014-03-13)
Limits
Total Time: 60000 MS | Test Time: 6000 MS |Memory: 62 MB | Output: 64 MB | Size: 14 KB
Enabled languages
Available in

Description

GusGus wants to give Jerry a new coat able to withstand a temperature of at most t (0 <= t <= 10^9) degrees, so he can go through the tunnels that have been built under the house of Tom. The tunnels always connect two ladders, which allow to go up to ground level. The tunnels may be traversed in either direction and each has a set temperature Ti(1 <= Ti <= 10^9) due to the depth to which it is, ensures that all the tunnels will have different temperatures. Travelling through a tunnel with a temperature higher than supported by the protective coat can cause death.


Jerry when moving through the tunnels always travels along a path in which the maximum temperature of the road is as small as possible, so he asks for help from you. He wants to know the number of different ways in which you can travel avoiding death. To simplify matters, the task takes into account only the beginning and the end of a road.
;jsessionid=6E55E570257CCBE3136BD0D871325311

GusGus wants to give Jerry a new coat able to withstand a temperature of at most t (0 <= t <= 10^9) degrees, so he can go through the tunnels that have been built under the house of Tom. The tunnels always connect two ladders, which allow to go up to ground level. The tunnels may be traversed in either direction and each has a set temperature Ti(1 <= Ti <= 10^9) due to the depth to which it is, ensures that all the tunnels will have different temperatures. Travelling through a tunnel with a temperature higher than supported by the protective coat can cause death.


Jerry when moving through the tunnels always travels along a path in which the maximum temperature of the road is as small as possible, so he asks for help from you. He wants to know the number of different ways in which you can travel avoiding death. To simplify matters, the task takes into account only the beginning and the end of a road.
;jsessionid=6E55E570257CCBE3136BD0D871325311

GusGus wants to give Jerry a new coat able to withstand a temperature of at most t (0 <= t <= 10^9) degrees, so he can go through the tunnels that have been built under the house of Tom. The tunnels always connect two ladders, which allow to go up to ground level. The tunnels may be traversed in either direction and each has a set temperature Ti(1 <= Ti <= 10^9) due to the depth to which it is, ensures that all the tunnels will have different temperatures. Travelling through a tunnel with a temperature higher than supported by the protective coat can cause death.


Jerry when moving through the tunnels always travels along a path in which the maximum temperature of the road is as small as possible, so he asks for help from you. He wants to know the number of different ways in which you can travel avoiding death. To simplify matters, the task takes into account only the beginning and the end of a road.
;jsessionid=6E55E570257CCBE3136BD0D871325311

Input specification

The input consists of a number of cases, each case starts with an integer M (1 <= M <= 10^5) representing the number of tunnels that exist, the following M lines contain three integers X, Y, Ti the description of a tunnel between the ladders X and Y with a temperature of Ti degrees, 1 <= X,Y <= 2^15. The next line contains a number Q (1 <= Q <= 10^5), the number of coats in the closet of GusGus, followed by Q lines with the temperature each coat can protect from.
;jsessionid=6E55E570257CCBE3136BD0D871325311
The input consists of a number of cases, each case starts with an integer M (1 <= M <= 10^5) representing the number of tunnels that exist, the following M lines contain three integers X, Y, Ti the description of a tunnel between the ladders X and Y with a temperature of Ti degrees, 1 <= X,Y <= 2^15. The next line contains a number Q (1 <= Q <= 10^5), the number of coats in the closet of GusGus, followed by Q lines with the temperature each coat can protect from.
;jsessionid=6E55E570257CCBE3136BD0D871325311
The input consists of a number of cases, each case starts with an integer M (1 <= M <= 10^5) representing the number of tunnels that exist, the following M lines contain three integers X, Y, Ti the description of a tunnel between the ladders X and Y with a temperature of Ti degrees, 1 <= X,Y <= 2^15. The next line contains a number Q (1 <= Q <= 10^5), the number of coats in the closet of GusGus, followed by Q lines with the temperature each coat can protect from.
;jsessionid=6E55E570257CCBE3136BD0D871325311

Output specification

For each coat S answer how many pairs <A,B> (A < B) of ladders Jerry can select such that there is a path from the ladder A to the ladder B that Jerry can take if GusGus gives him the layer S.

;jsessionid=6E55E570257CCBE3136BD0D871325311

For each coat S answer how many pairs <A,B> (A < B) of ladders Jerry can select such that there is a path from the ladder A to the ladder B that Jerry can take if GusGus gives him the layer S.

;jsessionid=6E55E570257CCBE3136BD0D871325311
The input consists of a number of cases, each case starts with an integer M (1 <= M <= 10^5) representing the number of tunnels that exist, the following M lines contain three integers X, Y, Ti the description of a tunnel between the ladders X and Y with a temperature of Ti degrees, 1 <= X,Y <= 2^15. The next line contains a number Q (1 <= Q <= 10^5), the number of coats in the closet of GusGus, followed by Q lines with the temperature each coat can protect from.
;jsessionid=6E55E570257CCBE3136BD0D871325311

Sample input

5
1 2 1
1 3 5
1 4 4
2 3 2
3 4 3
3
10
2
1

Sample output

6
3
1

Hint(s)

http://coj.uci.cu/24h/
http://coj.uci.cu/24h/
http://coj.uci.cu/24h/

Recommendation

We have carefully selected several similar problems: 2901 | 2482 | 4060 | 2350 | 1841 | 3092