Illuminati Spotti

One of Xxayvier’s favorite pastimes is spotting triangles due to his obsession with the Illuminati. Xxayvier has taken it to the extreme and has been trying to spot triangles on the larger scale.

He believes that the Illuminati has control of all cities which have $3$ undirected flights connecting to each other in a triangle shape. To test this theory, Xxayvier has been making maps listing undirected flights that connect from city $i$ to city $j$. He then tries to find the triangles from the map afterwards.

Because of the large number of cities that Xxayvier has listed, it has been very difficult keeping track and finding them all. Can you help him find the number of triangles made without duplicates?


Input consists of $N+1$ lines. The first contains the number of cities that you are given $N$ ($2 \leq N \leq 500$). The next $N$ input lines represent a city $i$ and the undirected flight that connects to another city $j$. Each line has $N$ numbers each number representing a city $j$ in ascending order. Each number can be either a $1$ in which a flight towards city $j$ exists or a $0$ meaning the flight does not exist.


Given that the triangles are created only by $3$ connecting cities, output the number of triangles the map can have without repeats.

Sample Input 1 Sample Output 1
0 1 1 0 
1 0 1 1 
1 1 0 1 
0 1 1 0 
Sample Input 2 Sample Output 2
0 1 1 0 1 
1 0 1 1 0 
1 1 0 1 1 
0 1 1 0 0 
1 0 1 0 0 
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 4.2Medium
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in