P9980 [USACO23DEC] Flight Routes G

Bessie recently found out that her favorite rock artist, Elsie Swift, is performing her newest “Eras Tour” concert. Unfortunately, the tickets sold out too quickly, so Bessie is considering flying to another city to attend the concert. The “Eras Tour” will be held in $N$ cities numbered $1 \dots N$ ($2 \le N \le 750$). For each pair of cities $(i, j)$ with $i < j$, there may exist a **one-way direct flight** from $i$ to $j$. A **route** from city $a$ to city $b$ is a sequence of $k \ge 2$ cities $a = c_1 < c_2 < \cdots < c_k = b$, such that for all $1 \le i < k$, there is a **one-way direct flight** from city $c_i$ to city $c_{i+1}$. For every pair of cities $(i, j)$ with $i < j$, you are given the parity of the number of routes between them ($0$ means even, $1$ means odd). While planning her travel itinerary, Bessie got distracted. Now she wants to know how many pairs of cities have a **one-way direct flight**. It can be proven that the answer is unique.

The first line contains an integer $N$. The next $N - 1$ lines follow. Line $i$ contains $N - i$ integers. The $j$-th integer on line $i$ represents the parity of the number of routes from city $i$ to city $i + j$.

Output the number of city pairs that have a one-way direct flight.

### Sample Explanation 1 There are two one-way direct flights: $1 \rightarrow 2$ and $2 \rightarrow 3$. There is one route between cities $1,2$ and one route between cities $2,3$, each consisting of exactly one one-way direct flight. There is also one route between cities $1,3$ ($1 \rightarrow 2 \rightarrow 3$). ### Sample Explanation 2 There are six one-way direct flights: $1 \rightarrow 2$, $1 \rightarrow 4$, $1 \rightarrow 5$, $2 \rightarrow 3$, $3 \rightarrow 5$, $4 \rightarrow 5$. This leads to the following numbers of routes: | From \ To | 1 | 2 | 3 | 4 | 5 | | :-: | :-: | :-: | :-: | :-: | :-: | | 1 | 0 | 1 | 1 | 1 | 3 | | 2 | 0 | 0 | 1 | 0 | 1 | | 3 | 0 | 0 | 0 | 0 | 1 | | 4 | 0 | 0 | 0 | 0 | 1 | | 5 | 0 | 0 | 0 | 0 | 0 | This matches the input. ### Test Point Properties - Test points $3 - 4$ satisfy $N \le 6$. - Test points $5 - 12$ satisfy $N \le 100$. - Test points $13 - 22$ have no additional constraints. Translated by ChatGPT 5