Ministarstvo
레이팅 미적용의견: 0
Croatian Olympiad in Informatics
April \(28^{st}\) 2024
After a successful career in a party we won’t name, Pero got a job at the Ministry of Tourism. Pero
oversees a network of \(N\) cities, labeled with numbers from 1 to \(N\), where there is exactly one, o\(ne-wa\)y
road between each pair of cities. In order to increase revenue, he has decided to introduce permits for
traffic. Pero would prefer to introduce a special permit for each road, but that would alert his superiors.
Therefore, he will introduce \(K\) different permits, labeled from 1 to \(K\), and possession of a specific permit
will be required to travel on each road.
To still ensure substantial revenue, Pero will settle for the following property.
• For each city \(v\), there is some city \(u\), such that it is not possible to travel from city \(v\) to city \(u\) with
just one permit.
Pero asks for your help to determine the minimum \(K\) such that there exists an assignment of permits
with the desired property, if such an assignment exists! If no such assignment exists, outp\(ut -1\).
In all subtasks, \(2 \le N \le 1000\). In each subtask, 15% of the points come from only deciding whether such
an assignment exists or not. For these points, if you don’t outp\(ut -1\), you need to output some assignment,
but it doesn’t have to satisfy Pero’s desired property.
Subtask
Score
Constraints
1
20
\(N \le 5\)
2
80
No additional constraints.
Croatian Olympiad in Informatics
April \(28^{st}\) 2024
The first line contains a positive integer \(N\).
The \(i-th\) of the following \(N\) lines contains \(N\) numbers \(a\)i,j where \(a\)i,\(j = 1\) if there is a road from city \(i\) to
city \(j\). Note that \(a_{i,i} = 0\) and for \(i\)̸ = \(j\), exactly one of the numbers \(a_{i,j}\) and \(a_{j,i}\) is n\(on-ze\)ro.
If there is no assignment with the desired property, outp\(ut -1\) in the first and only line.
Otherwise, output the minimum positive integer \(K\) in the first line.
In the following \(N\) lines, output the description of the assignment.
In the \(i-th\) line, output \(N\) numbers \(b_{i,j}\) where if \(a_{i,j} = 0\), then \(b_{i,j} = 0\), otherwise \(1 \le b_{i,j} \le K\) indicating
which permit is required for traveling on that road.
3
0 1 0
0 0 1
1 0 03
0 1 0
0 0 2
3 0 03
0 1 1
0 0 1
0 0 0-14
0 1 0 1
0 0 1 1
1 0 0 0
0 0 1 03
0 1 0 1
0 0 2 3
3 0 0 0
0 0 2 0Explanation for the third sample test:
Roads requiring the first permit are marked in red, the second permit in blue, and the third permit in
green.
From city 1, it is not possible to reach city 3 using just one permit.
From city 2, it is not possible to reach city 1 using just one permit.
From city 3, it is not possible to reach city 2 using just one permit.
From city 4, it is not possible to reach city 1 using just one permit.
평가 및 의견
Ministarstvo
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Ministarstvo