## IOI '14 P3 - Game

View as PDF

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 256M

Problem type
Allowed languages
C, C++

Jian-Jia is a young boy who loves playing games. When he is asked a question, he prefers playing games rather than answering directly. Jian-Jia met his friend Mei-Yu and told her about the flight network in Taiwan. There are cities in Taiwan (numbered ), some of which are connected by flights. Each flight connects two cities and can be taken in both directions.

Mei-Yu asked Jian-Jia whether it is possible to go between any two cities by plane (either directly or indirectly). Jian-Jia did not want to reveal the answer, but instead suggested to play a game. Mei-Yu can ask him questions of the form "Are cities and directly connected with a flight?", and Jian-Jia will answer such questions immediately. Mei-Yu will ask about every pair of cities exactly once, giving questions in total. Mei-Yu wins the game if, after obtaining the answers to the first questions for some , she can infer whether or not it is possible to travel between every pair of cities by flights (either directly or indirectly). Otherwise, that is, if she needs all questions, then the winner is Jian-Jia.

In order for the game to be more fun for Jian-Jia, the friends agreed that he may forget about the real Taiwanese flight network, and invent the network as the game progresses, choosing his answers based on Mei-Yu's previous questions. Your task is to help Jian-Jia win the game, by deciding how he should answer the questions.

#### Examples

We explain the game rules with three examples. Each example has cities and rounds of question and answer.

In the first example (the following table), Jian-Jia loses because after round 4, Mei-Yu knows for certain that one can travel between any two cities by flights, no matter how Jian-Jia answers questions 5 or 6.

10, 1yes
23, 0yes
31, 2no
40, 2yes
53, 1no
62, 3no

In the next example, Mei-Yu can prove after round 3 that no matter how Jian-Jia answers questions 4, 5, or 6, one cannot travel between cities 0 and 1 by flights, so Jian-Jia loses again.

10, 3no
22, 0no
30, 1no
41, 2yes
51, 3yes
62, 3yes

In the final example Mei-Yu cannot determine whether one can travel between any two cities by flights until all six questions are answered, so Jian-Jia wins the game. Specifically, because Jian-Jia answered yes to the last question (in the following table), then it is possible to travel between any pair of cities. However, if Jian-Jia had answered no to the last question instead then it would be impossible.

10, 3no
21, 0yes
30, 2no
43, 1yes
51, 2no
62, 3yes

Please write a program that helps Jian-Jia win the game. Note that neither Mei-Yu nor Jian-Jia knows the strategy of each other. Mei-Yu can ask about pairs of cities in any order, and Jian-Jia must answer them immediately without knowing the future questions. You need to implement the following two functions.

• initialize(n) – We will call your initialize first. The parameter is the number of cities.
• hasEdge(u, v) – Then we will call hasEdge for times. These calls represent Mei-Yu's questions, in the order that she asks them. You must answer whether there is a direct flight between cities and . Specifically, the return value should be 1 if there is a direct flight, or 0 otherwise.

Each subtask consists of several games. You will only get points for a subtask if your program wins all of the games for Jian-Jia.

115
227
358

#### Implementation details

Your submission implements the subprograms described above using the following signatures.

void initialize(int n);
int hasEdge(int u, int v);