程序设计在线评测(Online Judge)

2017年湖南科技大学大学生计算机程序设计竞赛即将于12月举行!

问题 1059. -- 2010欧洲西南分区赛:Comparing answers

1059: 2010欧洲西南分区赛:Comparing answers

时间限制: 10 Sec  内存限制: 128 MB
提交: 3  解决: 2
[提交][状态][讨论版]

题目描述

In a place in Southwestern Europe, the name of which I do not wish to recall, not long ago there were n
cities connected by unidirectional roads, with possibly more than one road connecting a city to another one,
or even to itself. As a homework assignment for your geography class, you need to calculate the number of
paths of length exactly two that were between each pair of cities. However, you've been too busy celebrating
the Spanish victory in the World Cup, so now you are copying the answers from your friend. You would like
to make sure his answers are correct before handing in your homework.

输入

The input consists of several test cases, separated by single blank lines. Each test case begins with a line
containing the integer n (1 <= n <= 1 000). The following n lines contain n elements each, with element j of
line i being the number of roads from city i to city j (a number between 0 and 10, inclusive). After that,
there will be n lines. Each will contain n elements, with element j of line i being the answer from your friend
for the number of length-2 paths from city i to city j; it will be an integer between 0 and 100 000 inclusive.
The test cases will nish with a line containing only the number zero (also preceded by a blank line).
Note: Large input le; use fast I/O routines.

输出

For each case, your program should output a line. The content of this line should be YES if your classmate's
solution to the assignment is right, and NO otherwise.

样例输入

3
2 0 1
1 0 3
1 1 0
5 1 2
5 3 1
3 0 4

3
2 0 1
1 0 3
1 1 0
5 1 2
5 3 2
3 0 4

0

样例输出

YES
NO

提示

来源

[提交][状态][讨论版]