## 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.

1 0, 1 yes
2 3, 0 yes
3 1, 2 no
4 0, 2 yes
----- -------- ------
5 3, 1 no
6 2, 3 no

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.

1 0, 3 no
2 2, 0 no
3 0, 1 no
----- -------- ------
4 1, 2 yes
5 1, 3 yes
6 2, 3 yes

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.

1 0, 3 no
2 1, 0 yes
3 0, 2 no
4 3, 1 yes
5 1, 2 no
6 2, 3 yes

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.

1 15
2 27
3 58

#### Implementation details

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

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


• commented on Dec. 3, 2020, 10:34 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Sept. 7, 2020, 9:33 p.m.

Nice..

• commented on Aug. 22, 2018, 12:55 p.m. edited

zubec has pointed out the grader is incorrect, and all submissions have been rejudged.

Credit to george_chen for identifying the bug.

• commented on Oct. 19, 2017, 7:46 p.m.

I don't think the math is showing up properly. I'm getting

(4 \le n \le 1\,500)

in the constraints

• commented on Oct. 20, 2017, 11:57 a.m.

Fixed.

• commented on Oct. 19, 2017, 10:28 p.m.

• commented on July 8, 2015, 10:40 p.m.

It should be r = (n)(n-1) / 2.

• commented on July 9, 2015, 9:36 a.m.

Fixed.