Editorial for COCI '22 Contest 3 #5 Skrivača
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, notice that if as soon as Marin enters room
the game ends. Also if
is adjacent
to
Marin can first go to room
and in the next move enter room
and the game ends. In the only
remaining case it is enough to check only the last step of the game, if in his last move Marin goes from
room
to room
we need to check if Luka can get from room
to room
without passing through
room
. For that it is enough to remove vertex
from the graph and check if
and
are connected with
a standard dfs algorithm. Now that we know all possible last moves we can easily calculate how many
moves are necessary to end the game from each starting room using bfs. Since there are
possible last
moves (one for each direction of each edge), and dfs and bfs run in
time complexity, the total
time complexity of this approach is
.
In the second subtask, the graph is a tree so to check if is connected to
after removing vertex
we
can use LCA which has a time complexity of
.
Consider nor
is adjacent to
, the game can only end in articulation points. Furthermore,
since for each articulation point it is fairly easy to construct a hiding strategy for which the game can
end in that vertex, we conclude that the second part of the third subtask is equivalent to: "There are at
most
articulation points." We can find articulation points using dfs spanning tree in time complexity of
. Since there are at most
of them, for each articulation point
we can check if
is connected
to
with dfs similar to the first subtask.
For the complete solution, we need to check if vertices and
are connected after removing vertex
faster.
In dfs spanning tree consider times of entry for each vertex in the same connected component with respect
to some articulation point
. It holds that times of entry of every vertex in some connected component
that is not connected to the root of dfs spanning tree form a continuous interval. The claim follows from
the fact that dfs visits all nodes from some connected component before recursively backtracking back to
the articulation point. Now we can determine in which interval some node belongs using binary search,
and if it doesn't belong to any interval we know it is in the component connected to the root of dfs
spanning tree. Time complexity of such an approach is
. For implementation details refer to
the attached source code.
In the attached source codes there will also be an alternative solution to this problem.
(Note that the source codes are available on the COCI website)
Comments