codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2172M.md (2513B)


      1 Source: https://codeforces.com/problemset/problem/2172/M
      2 
      3 M. Maximum Distance To Port
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 There are $n$ cities numbered from $1$ to $n$, connected by $m$ bidirectional roads, each exactly $1$ kilometer long. The road network forms a connected simple graph.
     22 
     23 Each city produces exactly one of $k$ types of agricultural products, numbered from $1$ to $k$. City $1$ is the main port where all products must be delivered.
     24 
     25 The government wants to estimate the worst-case transportation cost and time for exporting agricultural goods. To achieve this, they need to determine, for each product type, the longest among the shortest distances (in kilometers) from any city producing that product to the port city.
     26 
     27 Your task is to compute this maximum shortest distance for each product type.
     28 
     29  ![](https://espresso.codeforces.com/428d59e252593d564adc0f9357a0ae3c32372a12.png) Figure 1: An illustration for sample input 2.
     30 
     31 Input
     32 
     33 The first line contains three integers $n$, $m$, and $k$, representing the number of cities, bidirectional roads, and product types, respectively.
     34 
     35 The second line contains $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ is the product type produced by city $i$.
     36 
     37 The $i$-th of the following $m$ lines contains two integers $u_i$ and $v_i$, representing that the $i$-th bidirectional road connects cities $u_i$ and $v_i$.
     38 
     39 * $1 \leq n \leq 2 \times 10^{5}$
     40 * $0 \leq m \leq 2 \times 10^{5}$
     41 * $1 \leq k \leq n$
     42 * $1 \leq a_i \leq k$
     43 * $1 \leq u_i, v_i \leq n$
     44 * The graph is connected and simple (no self-loops or multiple edges).
     45 * Every product type from $1$ to $k$ is produced by at least one city.
     46 
     47 Output
     48 
     49 Output $k$ integers in a single line. The $i$-th integer should be the maximum shortest distance (in kilometers) from any city producing product $i$ to the port city $1$.
     50 
     51 Examples
     52 
     53 Input
     54 
     55 ```
     56 3 3 2
     57 
     58 2 1 1
     59 
     60 1 2
     61 
     62 3 1
     63 
     64 3 2
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 1 0
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 8 10 5
     77 
     78 5 1 1 2 4 4 2 3
     79 
     80 8 2
     81 
     82 4 6
     83 
     84 6 2
     85 
     86 5 2
     87 
     88 2 7
     89 
     90 8 6
     91 
     92 1 2
     93 
     94 7 6
     95 
     96 3 1
     97 
     98 1 5
     99 ```
    100 
    101 Output
    102 
    103 ```
    104 1 3 2 2 0
    105 ```
    106 
    107 Note
    108 
    109 Explanation of Example 2: Figure 1 illustrates this example. In this example, the port is the blue node. All goods of product type 5 are already in the port, so their transportation cost is 0. The transportation cost for product type 4 is higher. One city with product type 4 has a distance of 1 to the port, while another one has a distance 2. Therefore, the transportation cost is 2.