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=BF8202D9A64107113730B9B39D6A5CA6

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=BF8202D9A64107113730B9B39D6A5CA6

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=BF8202D9A64107113730B9B39D6A5CA6

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=BF8202D9A64107113730B9B39D6A5CA6
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=BF8202D9A64107113730B9B39D6A5CA6
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=BF8202D9A64107113730B9B39D6A5CA6

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=BF8202D9A64107113730B9B39D6A5CA6

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=BF8202D9A64107113730B9B39D6A5CA6
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=BF8202D9A64107113730B9B39D6A5CA6

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: 4192 | 3262 | 3656 | 2675 | 3657 | 2819