Tenis
레이팅 미적용의견: 0
Croatian Olympiad in Informatics 2019.
Page 8 of 9
Vito loves tennis. Soon, he will organize a huge tournament with N participating players, denoted 1, 2,
..., N. Vito has followed the players' statistics in the last couple of years. Thus, he has determined their
strenghts on three different court surfaces: clay, grass, and hardcourt. Namely, for each surface he has
determined the players' ranking list, from the strongest to the weakest player on that surface.
The rules of Vito's tournament are quite unusual. A total of N – 1 matches will be played. In each
match, two players that have not yet been eliminated will play against each other on a particular court
surface. The player who is weaker on that surface will lose the match and thus be eliminated from the
tournament. The only player who remains in the tournament after all N – 1 matches will be the winner
of the tournament.
Vito is an influential man and can manipulate the outcome of the tournament. Namely, for each match
of the tournament, Vito can choose both players and the court surface of the match. Of course, he can
only choose players which have not been eliminated yet.
Vito often updates the statistics in his books in such a way that he sometimes swaps the positions of
two players in a particular surface's ranking list. Besides, Vito has a lot of friends, some of which come
to him with questions like this: Player X is my nephew, is there any chance he will win the tournament
(wink, wink)? To answer their queries, Vito has made you an offer which is hard to refuse. You should
write a program which will update the ranking lists and answer the questions of Vito's friends based on
the ranking lists at that moment.
subtask
points
additional constraints
1
7
\(N \le 15\), \(Q \le 10\)
2
11
\(N \le 1000\), \(Q \le 10\)
3
12
\(Q \le 10\)
4
21
all events are of type 1
5
49
no additional constraints
Croatian Olympiad in Informatics 2019.
Page 9 of 9
The first line contains integers N and Q (\(1 \le N\), \(Q \le 100\,000\)), the number of players and the number
of events.
Each of the next three lines contains a permutation of integers {1, 2, ..., N} — the ranking of players
on a particular court surface, from the strongest to the weakest one.
Each of the following Q lines is of one of the following types:
• “1 X”, where \(1 \le X \le N\) — Vito's friend wants to know if player X can win the tournament.
• “2 P A B”, where \(1 \le P \le 3\) and \(1 \le A \ne B \le N\) — Vito has realised that he should swap the
positions of players A and B in the P^{th} ranking list.
For each query of type 1, output “DA” or “NE” (Croatian words for “YES” and “NO”) in a separate
line.
4 4
1 2 3 4
2 1 3 4
2 4 3 1
1 1
1 4
2 3 1 4
1 4DA
DA
NE6 7
4 6 1 5 3 2
5 1 4 2 6 3
4 6 1 5 2 3
1 2
2 2 4 5
1 1
2 2 4 5
2 2 5 6
1 2
1 1DA
NE
NE
DA
First sample description:
If all matches are played on the first court surface, player 1 will win the tournament.
Example of a tournament where player 4 wins:
• Players 3 and 4 play on the third court surface – player 4 wins.
• Players 1 and 2 play on the first court surface – player 1 wins.
• Players 1 and 4 play on the third court surface – player 4 wins.
After updating the third court surface's ranking list (new ranking: 2 1 3 4), player 4 is the weakest on all
surfaces and thus cannot win the tournament.평가 및 의견
Tenis
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Tenis