20389번 - ICC 서브태스크다국어언어 제한함수 구현

Astro the astronaut just started his internship on the International Space Station (ISS). His job is to study the Terran civilization from the planet Mar Sara. The Terrans already built N cities, numered from 1 to N, but they did not build any roads between them.

Just as Astro started his internship, the Terrans began building roads on Mar Sara. It's known that the Terrans want to connect the cities as fast as possible, so they won't build a road between 2 cities that are already connected by a path composed of one or more roads. Each time the Terrans build a new road, Astro wants to know what cities it connects before the next road is built.

Luckily for Astro, he has access to SETI Masterpieces, a new satellite that can look at Mar Sara and see what roads have been built. Given two disjoint sets of cities, SETI is able to tell whether there is at least one direct road that connects a city from the first set with another city from the second set.

The way the interaction works is the following:

1. The Terrans build a road.
2. Astro uses SETI to try to discover the newly built road.
3. He goes to the ISS Scientific Committee and shows them his answer for the newly created road.
4. If there are less than N - 1 roads build, repeat from step 1.

Your job is to write a program that will solve Astro's problem.

You should implement a function run() which will be called once, in the beginning of the program. From this function, you should call query() every time you use the SETI Masterpieces. Every time you determine the newest built road, you should call setRoad(). You can call query() multiple times before calling setRoad().

Grader function: query()

• C/C++: int query(int size_a, int size_b, int a[], int b[]);

Call this function to make a query to the SETI Masterpieces. Arguments size_a and size_b should represent the sizes of the two sets that are queried. Arrays a[] and b[] should contain the indices of the cities from the first and second set, respectively. Note that these sets should be disjoint! The function returns 1 if there is at least one direct road between a city from the first set and a city from the second set, and 0 otherwise.

Grader procedure: setRoad()

• C/C++: void setRoad(int a, int b);

Call this procedure to indicate that you discovered that the newest road connects cities a and b. If the road is incorrectly discovered, you will receive 0 points for the current test case and the program terminates. If this is the (N-1)^th call to this procedure, the program terminates and returns the score for the current test case. Otherwise, a new road is built by the Terrans and the interaction continues. Any other subsequent call to query() will take into account the road built after the call to setRoad().

Your procedure: run()

• C/C++: void run(int N);

Your submission must implement this procedure. You must alternately call query() and setRoad() from this procedure. The received argument N represents the number of cities built by the Terrans. If this procedure finishes its execution before guessing all the roads, you will not receive credit for that test case.

Language notes

• C/C++: you must #include "icc.h"

• icc.h