Izlet
레이팅 미적용의견: 0
Croatian Olympiad in Informatics 2019.
Page 2 of 9
When a competitive programmer thinks of a tree, it's not the same tree that a regural person thinks of.
Luckily, in this task, both meanings are correct.
Nikola loves nature and often walks in the woods, looking at the trees and admiring their size, node
degrees, paradoxically regular randomness, etc. In this day of lovely spring, there are even more reasons
to look above into these magnificent creatures: the trees are full of color and that captured Nikola's
attention.
So one day he observed a large tree with N nodes, seeing a color in each node. Was there a flower, an
animal, or Nikola simply went mad, it's hard to say. But he was looking at that tree for a very long time,
and in an \(N \times N\) matrix he wrote, for each two nodes, the number of distinct colors on a unique
simple path between (and including) these two nodes. Sadly, by admiring all those colors, Nikola
completely forgot what the tree looked like and which colors were in the nodes.
So he needs your help. From the matrix he wrote, determine a possible tree and possible colors of the
respective nodes. Colors should be denoted by numbers from {1, 2, ..., N}. It is guaranteed that
Nikola did not make a mistake; in other words, a solution will exist.
subtask
points
additional constraints
1
18
all numbers in the matrix equal 1 or 2
2
25
there is a solution where the tree is a chain of
nodes 1, 2, ..., N in that order, i.e., the edges are
(\(i\), \(i + 1\)) for each \(i = 1\), ..., N – 1
3
57
no additional constraints
(See examples on the next page.)
Croatian Olympiad in Informatics 2019.
Page 3 of 9
The first line contains a subtask number (1, 2 or 3) from the Scoring section below.
The second line contains an integer N (\(1 \le N \le 3000\)), the number of nodes in the tree, which are
denoted 1, 2, ..., N.
Each of the next N lines contains N integers, where \(j-th\) number in \(i-th\) line equals the number of
distinct colors on the path from node \(i\) to node \(j\).
The first line should contain N spa\(ce-se\)parated integers between 1 and N: colors of the nodes 1, 2, ...,
N.
Each of the next N – 1 lines should contain two integers A, B representing the edge (neighboring
nodes) in the tree. Order of the edges and nodes inside an edge is arbitrary.
3
5
1 2 2 2 3
2 1 3 3 2
2 3 1 3 4
2 3 3 1 3
3 2 4 3 11 2 3 4 4
1 2
1 3
1 4
2 52
4
1 2 3 3
2 1 2 2
3 2 1 2
3 2 2 11 2 3 2
1 2
2 3
3 41
5
1 2 2 2 2
2 1 1 2 2
2 1 1 2 2
2 2 2 1 2
2 2 2 2 11 2 2 1 2
1 2
2 3
2 4
1 5평가 및 의견
Izlet
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Izlet