AqaAsadiSaves
SRM 787 · 2020-06-17 · by a.poorakhavan
Problem Statement
The devil is coming to INOI land. INOI land has N cities and M bidirectional roads between them. Each road connects either one city to itself, or two distinct cities to each other. Each pair of cities can be connected by multiple roads. (I.e., INOI is a graph in which both self-loops and multiple edges may appear.)
The devil wants to destroy one road. The devil will always choose the road whose destruction will cause the most damage. The damage caused by the destruction of a road is the number of (unordered) pairs of cities that will get disconnected when the road is destroyed.
Aqa Asadi, as the hero of INOI, wants to prevent as much damage as possible. The night before the devil attacks, Aqa Asadi can build one additional road. The devil will then consider the new road network (including the road Aqa Asadi built) when choosing which road he should destroy. Calculate and return the smallest possible amount of damage done by the devil.
Use the pseudocode below to generate two arrays A and B with M elements each. For each valid i, one of the roads in INOI land connects cities A[i] and B[i].
A = PA
B = PB
for i = size(PA) to M-1:
A.append( Seed )
Seed = (Seed * X + Y) modulo N
for i = size(PB) to M-1:
B.append( Seed )
Seed = (Seed * X + Y) modulo N
Notes
- The road added by Aqa Asadi can connect any two cities, even if they are already connected by one or more other roads. Alternately, he may also choose to build a self-loop at any city.
Constraints
- N will be between 1 and 200,000, inclusive.
- M will be between 1 and 200,000, inclusive.
- PA and PB will have the same number of elements.
- PA will have at most M elements.
- PA will have at most 500 elements.
- Elements of PA and PB will be between 0 and N-1, inclusive.
- Seed, X, Y will each be between 0 and N-1, inclusive.
3
3
{0, 1, 2}
{1, 2, 0}
0
0
0
Returns: 0
7
6
{0, 1, 2, 2, 4, 4}
{1, 2, 3, 4, 5, 6}
0
0
0
Returns: 6
1913
1500
{}
{}
0
3
1
Returns: 6
1913
1500
{0, 1, 2}
{1, 2, 0}
0
3
1
Returns: 36
1913
1000
{}
{}
0
3
1
Returns: 2
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AqaAsadiSaves with a public method long long minDamage(int N, int M, vector<int> PA, vector<int> PB, int Seed, int X, int Y) · 88 test cases · 2 s / 256 MB per case