Problem 3508 --I do not know Graph Theory!

3508: I do not know Graph Theory!

正确率: $0.00\%$ 下一题

Time Limit	$1$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$0$	正确数量	$0$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签

Description

A tournament graph is a directed graph where there is exactly one edge between every two distinct vertices.
A strongly connected graph is a directed graph where there is a path between every two distinct vertices.
You are given a tournament graph. For each edge of the graph, find out whether the graph is strongly connected when that edge is reversed.

Input

The first line contains one integer

1≤T≤40000), the number of test cases.
For each test case, the first line contains one integer

2≤n≤5000), the number of vertices.
The next

n−1lines give out the compressed lower triangular matrix in the following way:
Each line contains an uppercase hexadecimal string, where the

j-th hexadecimal of the

i-th string

Si,j=∑3k=02k×Ei+1,4j+k−3, and

Ei,j=1iff the direction of the edge between

i,jis from

ito

j. All indices start from

1.
It is guaranteed that there are at most

3test cases in which the

nis larger than

10.

Output

For each test case, output

n−1lines in the same format of the input:

Si,j=∑3k=02k×ansi+1,4j+k−3, and

ansi,j=1iff the graph is strongly connected when the edge between

i,jis reversed.

Sample Input复制

Sample Output复制

赛题来源/所属竞赛 2020 Multi-University Training Contest 10 N/A

竞赛编号	竞赛名称	竞赛时间	访问比赛

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战