시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1 | 1 | 1 | 100.000% |
Once again, the river Seine has overflowed. As moving all the precious items out of the basements of the Louvre museum takes a considerable amount of time, you are tasked with forecasting at which time the Louvre risks to be flooded. This time, you will rely on a new model of propagation of the flood that provides a “worst-case scenario” prediction of how much flood there will be in each neighborhood of Paris.
In this model, Paris is represented as an undirected graph. The set of vertices V0, . . . , VN−1 corresponds to the various areas of Paris. For instance, the node V0 corresponds to the Seine and the node V1 to the Louvre. An edge (X,Y) indicates that water could flow directly from X to Y and from Y to X. However, due to gravity, the water flow will obviously depend on the altitude (A(X) and A(Y)) of both areas.
Your model relies on discrete time, which means you study the flood at T instants indexed from 0 to T − 1. In addition to the graph representing Paris, thanks to the engineers and meteorologists of the city, you also have access to some other data, used in the model:
Then you rely on your model to predict a maximum water level WL(n, t) that there can be at area n and at time 0 ≤ t < T.
The model is based on the following idea: if the water level is L in some area n at some instant t, then this water might flow at time t + 1 to all the areas that are neighbors of n (taking into account the altitude difference). Formally, WL(n, t) is defined as follows:
Your goal is to determine the smallest t (0 ≤ t < T) such that the Louvre can be flooded at this time t (that is, such that WL(1, t) > 0).
The input comprises several lines, each consisting of integers separated with single spaces:
All the altitudes, initial measurements, and forecasts are integers in the range between 0 and 1 000 000 000.
The output should consist of a single line, whose content is the smallest t such that the Louvre is flooded. If the Louvre is not flooded at a time t < T then your program should answer −1.
5 4 10 0 1 4 4 5 1 0 0 0 0 2 3 4 5 6 7 8 9 10 0 2 0 4 2 3 3 1
7
In the sample input above, there are 5 nodes, 4 edges and 10 predictions. The evolution of WL in depicted in the following array, which shows that the Louvre is flooded at time t = 7.
Areas: | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
t = 0 | 1 | 0 | 0 | 0 | 0 |
t = 1 | 2 | 0 | 0 | 0 | 0 |
t = 2 | 3 | 0 | 0 | 0 | 0 |
t = 3 | 4 | 0 | 0 | 0 | 0 |
t = 4 | 5 | 0 | 0 | 0 | 0 |
t = 5 | 6 | 0 | 1 | 0 | 0 |
t = 6 | 7 | 0 | 2 | 1 | 1 |
t = 7 | 8 | 4 | 3 | 2 | 2 |
t = 8 | 9 | 5 | 4 | 3 | 3 |
t = 9 | 10 | 6 | 5 | 4 | 4 |
5 4 5 0 2 4 1 1 1 0 0 1 0 2 3 4 5 0 2 2 1 4 3 3 1
-1
In the sample input above, there are 5 nodes, 4 edges, and 5 predictions. The evolution of WL in depicted in the following array, which shows that the Louvre does not get flooded in the studied period.
In the sample input above, there are 5 nodes, 4 edges and 10 predictions. The evolution of WL in depicted in the following array, which shows that the Louvre is flooded at time t = 7.
Areas: | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
t = 0 | 1 | 0 | 0 | 1 | 0 |
t = 1 | 2 | 0 | 0 | 1 | 1 |
t = 2 | 3 | 0 | 0 | 1 | 1 |
t = 3 | 4 | 0 | 0 | 1 | 1 |
t = 4 | 5 | 0 | 0 | 1 | 1 |
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2018 PB번