#PU1353. USACO 2023 December Contest, Gold — Problem 1. Flight Routes

    ID: 1289 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec23来源:usaco.orgscoring:equal_test_cases并查集

USACO 2023 December Contest, Gold — Problem 1. Flight Routes

USACO 2023 December Contest, Gold — Problem 1. Flight Routes

题目描述

Bessie recently discovered that her favorite pop artist, Elsie Swift, is performing in her new Eras Tour! Unfortunately, tickets are selling out fast, so Bessie is thinking of flying to another city to attend the concert. The Eras tour is happening in NN (2≤N≤7502\le N\le 750) cities labeled 1…N1\dots N, and for each pair of cities (i,j)(i,j) with i<ji<j there either exists a single direct flight from ii to jj or not. A flight route from city aa to city bb (a<ba<b) is a sequence of k≥2k\ge 2 cities a=c1<c2<⋯<ck=ba=c_1<c_2<\dots<c_k=b such that for each 1≤i<k1\le i<k, there is a direct flight from city cic_i to city ci+1c_{i+1}. For every pair of cities (i,j)(i,j) with i<ji<j, you are given the parity of the number of flight routes between them (0 for even, 1 for odd). While planning her travel itinerary, Bessie got distracted and now wants to know how many pairs of cities have direct flights between them. It can be shown that the answer is uniquely determined.

输入格式

The first line contains NN. Then follow N−1N-1 lines. The iith line contains N−iN-i integers. The jjth integer of the iith line is equal to the parity of the number of flight routes from ii to i+ji+j.

输出格式

(见题面原文)

数据范围

Inputs 3-4: N≤6N\le 6 Inputs 5-12: N≤100N\le 100 Inputs 13-22: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

3
11
1
2
There are two direct flights: $1\to 2$ and $2\to 3$. There is one flight route
from $1$ to $2$ and $2$ to $3$, each consisting of a single direct flight. There
is one flight route from $1$ to $3$ ($1\to 2\to 3$).

样例 2

5
1111
101
01
1
6
There are six direct flights $1\to 2, 1\to 4, 1\to 5, 2\to 3, 3\to 5, 4\to 5$.
These result in the following numbers of flight routes:
Flight Route Counts:

            dest
          1 2 3 4 5

       1  0 1 1 1 3 
       2  0 0 1 0 1 
source 3  0 0 0 0 1 
       4  0 0 0 0 1 
       5  0 0 0 0 0
which is equivalent to the sample input after taking all the numbers $\pmod{2}$.