ForbiddenStreets

SRM 679 · 2016-01-04 · by ltaravilse

SRM 679 · 2016-01-04 · by ltaravilse · Graph Theory

Show categories

Class Name: ForbiddenStreets

Return Type: int[]

Method Name: find

Arg Types: (int, vector<int>, vector<int>, vector<int>)

Problem Statement

The road network in the city of Nlogonia contains N intersections and M streets. The intersections are numbered 0 through N-1 and the streets are numbered 0 through M-1. All streets are bidirectional. Each street connects two distinct intersections. Each pair of intersections is directly connected by at most one street. The entire road network is connected: it is possible to get from any intersection to any other by following some roads.
You are given the description of this road network: the int N and three int[]s: A, B, and time. For each valid i, street i connects the intersections A[i] and B[i], and the time needed to traverse this street (in either direction) is time[i].
The major of Nlogonia wants to organize a parade. The parade will block off one of the city's streets. (Just the passage through the street will be blocked. It will still be possible to pass through the intersections connected by the street.)
For each unordered pair {X,Y} of intersections there is a single bus that drives back and forth between X and Y. The parade may cause delays for some of these buses. More precisely: the bus that connects X and Y will be affected if and only if the blockade increases the length of the shortest path between X and Y. This includes the case when the blockade makes travel between X and Y completely impossible.
The major needs to know the effect of blocking each street in the city. Return a int[] with M elements. Element i of the return value should be the number of buses that would be affected if the parade blocked the street number i.

Notes

This problem has an unusual time limit of 4 seconds.

Constraints

N will be between 1 and 100 inclusive.
A, B and time will contain M elements each.
M will be between 1 and 2000 inclusive.
Each element of A and B will be between 0 and N-1 inclusive.
There will not be any street connecting an intersection with itself.
Each pair of intersections will be directly connected by at most one street.
Each element of time will be between 1 and 1000 inclusive.
There will always be a path between each pair of intersections.

Examples

3
{0,1}
{1,2}
{1,1}
Returns: {2, 2 }

There are three intersections and two streets. Street 0 connects intersections 0 and 1, and street 1 connects intersections 1 and 2. There are three buses: one between 0 and 1, one between 1 and 2, and one between 0 and 2. The blockade of any street will influence two of these three buses. For example, if we block street 0, the 0-1 bus and the 0-2 bus will not be able to run at all.

4
{0,1,2}
{1,2,3}
{2,4,6}
Returns: {3, 4, 3 }

5
{0,0,0,0,1,1,1,2,2,3}
{1,2,3,4,2,3,4,3,4,4}
{1,2,3,4,5,6,7,8,9,10}
Returns: {4, 4, 4, 4, 0, 0, 0, 0, 0, 0 }

In this test case we have 5 intersections and 10 streets: each pair of intesections is connected by a direct street. This time, different streets have different lengths. Note that those direct streets don't always represent the shortest paths. For example, the optimal way of going from intersection 1 to intersection 2 goes through intersection 0. If the parade blocks the street between 2 and 4, no buses will be affected: for each bus, the shortest path between its two intersections will still have the same length. If the parade blocks the street between 0 and 3, four buses will be affected: the buses 0-3, 1-3, 2-3, and 3-4.

5
{0,0,0,0,1,1,1,2,2,3}
{1,2,3,4,2,3,4,3,4,4}
{1,2,1,2,1,2,1,2,1,2}
Returns: {1, 0, 1, 0, 1, 0, 1, 1, 1, 1 }

3
{0,1,2}
{1,2,0}
{1,2,3}
Returns: {1, 1, 0 }

Submissions are judged against all 41 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ForbiddenStreets with a public method vector<int> find(int N, vector<int> A, vector<int> B, vector<int> time) · 41 test cases · 2 s / 256 MB per case