## CCO '19 P3 - Winter Driving

View as PDF

Points: 30 (partial)
Time limit: 0.6s
Memory limit: 1G

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

In the Great White North, there are cities numbered from to . There are citizens living in city . There are roads numbered from to . Road connects city and city , where . There are at most roads connected to any city.

During winter, all roads will be converted into one-way highways due to dangerous driving conditions. That is, road will become a highway that is either one-way from city to city or one-way from city to city .

Every citizen wants to send a holiday card to every other citizen. Citizen can send a card to citizen if it is possible to travel from the city lives in to the city lives in using only highways.

What is the maximum number of holiday cards that can be sent after converting all roads to highways?

#### Input Specification

The first line contains one integer .

The second line contains integers .

The third line contains integers .

Let be the maximum number of roads connected to any city. It is guaranteed that .

For 5 of the 25 available marks, .

For an additional 5 of 25 available marks, and .

For an additional 5 of 25 available marks, .

For an additional 5 of 25 available marks, there will be 37 cities, where one city is connected to 36 other cities, and these other 36 cities are only connected to this one city.

#### Output Specification

Print one line with one integer, the maximum number of cards that can be sent after converting all roads to highways.

#### Sample Input

4
3 3 4 1
1 2 1

#### Output for Sample Input

67

#### Explanation of Output for Sample Input

One possible way of converting roads to highways is for road 2 to become one-way from city 2 to city 1, road 3 to become one-way from city 3 to city 2, and road 4 to become one-way from city 1 to city 4.

Consider the following pictures, with the cities and associated population (in parentheses) for the initial roads

and what it looks like after all roads are converted to highways:

Every citizen in city 3 can send 3 holiday cards to city 3 citizens, 3 holiday cards to city 2 citizens, 3 holiday cards to city 1 citizens, and 1 holiday card to the city 4 citizen, for a total of 40 holiday cards sent out of city 3.

Similarly,

• city 2 citizens send 6 holidays cards each, for a total of 18 holiday cards.
• city 1 citizens send 3 holidays cards each, for a total of 9 holiday cards.
• the city 4 citizen cannot send any holiday cards.

A total of holiday cards are sent.