The VIP Network#13056

The VIP Network (Editorial)

Let's look at the maximum possible congestion score. If no cities are upgraded to "VIP" status, every road has a score of $3$ . Thus, the initial total score of the network is $3 \cdot M$ 3 \cdot M.

What happens when Fady upgrades a single city $u$ to "VIP"?

Every road connected to city $u$ changes its state from (Standard–Standard) to (VIP–Standard). Its score drops from $3$ to $2$ . This decreases the total network score by $1$ for each road connected to $u$ .
If the city $v$ at the other end of a road is also upgraded to "VIP", the road state changes from (VIP–Standard) to (VIP–VIP). Its score drops from $2$ to $1$ . This decreases the total score by another $1$ .

Key Observation: Upgrading a city to "VIP" status independently reduces the total network score by exactly $1$ for every road connected to it. In graph terms, upgrading node $u$ reduces the total score by $degree (u)$ .

Therefore, to minimize the total congestion score, we must maximize the total reduction. We calculate the degree of all $N$ cities, sort them in descending order, and select the top $K$ cities.

Minimum Score = 3 \cdot M - i \in Top K \sum degree [i]

\text{Minimum Score} = 3 \cdot M - \sum_{i \in \text{Top } K} \text{degree}[i]

Complexity Analysis:

Time Complexity: $O (N lo g N + M)$ \mathcal{O}(N \log N + M) per test case due to sorting the node degrees.
Space Complexity: $O (N + M)$ \mathcal{O}(N + M) to store the adjacency list / degree table.

3 \cdot M

Minimum Score = 3 \cdot M - i \in Top K \sum degree [i]

O (N lo g N + M)

O (N + M)