17686번 - Airline Route Map 서브태스크점수다국어언어 제한함수 구현투 스텝피드백

Alice is living in JOI Kingdom. She will invite Bob, who is living in Republic of IOI. Before she invites him, she is planning to send the airline route map of JOI Kingdom to him. JOI Kingdom is an island country consisting of N islands, numbered from 0 to N−1. There are M airline routes in JOI Kingdom. For each i (0 ≤ i ≤ M−1), the (i + 1)-th airline route connects the island A_i and the island B_i, in both directions. No two airline routes connect the same two islands. She must use a special telegraph machine operated by JOI Kingdom. She can send an undirected graph using the telegraph machine. However, when she uses it, the numbers of the vertices and the number of the edges will be shuffled randomly.

Precisely, the information will be sent as follows. Let G be the graph sent by Alice. (Let V be the number of vertices of G, and U the number of edges of G.)

• Alice specifies the number of edges V of G, and the number of edges U of G. Then, she puts each of numbers 0, 1, . . . , V − 1 to each vertex, and each of numbers 0, 1, . . . , U − 1 to each edge.
• Alice specifies the parameters C₀, C₁, . . . , C_U−1 and D₀, D₁, . . . , D_U−1. These parameters describe the edges of G, i.e., for each j (0 ≤ j ≤ U − 1), the j-th edge of G connects the vertex C_j and the vertex D_j.
• The numbers of the vertices of G are shuffled by JOI Kingdom. First, JOI Kingdom generates a sequence p[0], p[1], . . . , p[V − 1], which is a permutation of 0, 1, . . . , V − 1. Then, C₀, C₁, . . . ,C_U−1 are replaced by p[C₀], p[C₁], . . . , p[C_U−1], and D₀, D₁, . . . , D_U−1 are replaced by p[D₀], p[D₁], . . . , p[D_U−1].
• Then, the numbers of the edges of G are shuffled by JOI Kingdom. First, JOI Kingdom generates a sequence q[0], q[1], . . . , q[U − 1] which is a permutation of 0, 1, . . . , U − 1. Then, C₀, C₁, . . . ,C_U−1 are replaced by Cq[0],Cq[1], . . . ,Cq[U−1], and D₀, D₁, . . . , D_U−1 are replaced by Dq[0], Dq[1], . . . , Dq[U−1].
• The following data are sent to Bob: the values of V and U, and the latest values of the parameters C₀, C₁, . . . , C_U−1 and D₀, D₁, . . . , D_U−1.

Note that only a simple graph can be sent using this telegraph machine. Here, a simple graph means a graph without multiple edges and self-loops.

In other words, she can send a graph satisfying the following conditions: (C_i, D_i) , (C_j, D_j) and (C_i, D_i) , (D_j, C_j) are satisfied for every i, j (0 ≤ i < j ≤ U − 1), and C_i, D_i is satisfied for every i (0 ≤ i ≤ U − 1).

Alice wants to send the airline route map of JOI Kingdom to Bob using a graph with minimum number of vertices.

In order to help communication between Alice and Bob, write the following two programs:

• Given the number of islands N in JOI Kingdom, the number of airline routes M in JOI Kingdom, and the sequences A, B representing the airline route map of JOI Kingdom, the first program outputs information of the graph G sent by Alice.
• Given information of the graph G received by Bob, the second program recovers the airline route map of JOI Kingdom.

You need to submit two files.

The first file is Alice.cpp. This file outputs information of the graph sent by Alice. It should implement the following function. The program should include Alicelib.h.

• void Alice( int N, int M, int A[], int B[] )
  For each test case, this function is called once.
  • The parameter N is the number of islands of JOI Kingdom.
  • The parameter M is the number of airline routes in JOI Kingdom.
  • The parameters A[], B[] are sequences of length M describing the airline route map of JOI Kingdom.

Using the following functions, the function Alice outputs information of the graph G sent by Alice.

• void InitG( int V, int U )
  This function specifies the number of vertices of G and the number of edges of G.
  • The parameter V is the number of vertices of G. The parameter V should be an integer between 1 and 1500, inclusive. If the call to this function has parameters outside this range, your program is considered as Wrong Answer [1].
  • The parameter U is the number of edges of G. The parameter U should be an integer between 0 and V(V − 1)/2, inclusive. If the call to this function has parameters outside this range, your program is considered as Wrong Answer [2].
• void MakeG( int pos, int C, int D )
  This function specifies the edges of G.
  • The parameter pos is the number of the edge specified by the call. The parameter pos should be an integer between 0 and U − 1, inclusive. If the call to this function has parameters outside this range, your program is considered as Wrong Answer [3]. This function should not be called more than once with the same parameter pos. If this function is called more than once with the same parameter, your program is considered as Wrong Answer [4].
  • The parameters C and D are the vertices of the edge pos of the graph G. C and D should be integers between 0 and V − 1, inclusive. Also, C ≠ D should be satisfied. If C or D does not satisfy these conditions, your program is considered as Wrong Answer [5].

Here, U and V are the integers specified by InitG.

In the function Alice, after calling the function InitG once, the function MakeG should be called exactly U times. If the function InitG is called twice, your program is considered as Wrong Answer [6]. If the function MakeG is called before the function InitG is called, your program is considered as Wrong Answer [7]. If InitG is not called when the function Alice terminates, or, the function MakeG is not called U times, your program is considered as Wrong Answer [8]. When the function Alice terminates, if the graph G described by Alice is not a simple graph, your program is considered as Wrong Answer [9].

If the call to the function Alice is considered Wrong Answer, your program is terminated immediately.

The second file is Bob.cpp. This file outputs, given information of the graph G received by Bob, the airline route map of JOI Kingdom. It should implement the following function. The program should include Boblib.h.

• void Bob( int V, int U, int C[], int D[] )
  For each test case, this function is called once.
  • The parameter V is the number of vertices of the graph G.
  • The parameter U is the number of edges of the graph G.
  • The parameters C[], D[] are sequences of length U describing the edges of the graph G.

Using the following functions, the function Bob recovers the airline route map of JOI Kingdom, and outputs information of the airline route map.

• void InitMap( int N, int M )
  This function specifies the number of islands of JOI Kingdom, and the number of airline routes in JOI Kingdom.
  • The parameter N is the recovered number of islands in JOI Kingdom. N is an integer which should be equal to the actual number of islands in JOI Kingdom. If they are not equal, your program is considered as Wrong Answer [10].
  • The parameter M is the recovered number of airline routes in JOI Kingdom. M is an integer which should be equal to the actual number of airline routes in JOI Kingdom. If they are not equal, your program is considered as Wrong Answer [11].
• void MakeMap( int A, int B )
  This function specifies the number of airline routes in JOI Kingdom.
  • The parameters A and B mean there is an airline route connecting the island A and the island B. A and B are integers between 0 and N − 1, inclusive. Also, A ≠ B should be satisfied. If A or B does not satisfy these conditions, your program is considered as Wrong Answer [12]. If there does not exist an airline route connecting the island A and the island B in JOI Kingdom, your program is considered as Wrong Answer [13]. The airline route described by a call to this function should be different from the airline routes of previous calls. When MakeMap( A, B ) is called, if either MakeMap( A, B ) or MakeMap( B, A ) was already called before, your program is considered as Wrong Answer [14].

Here, N is the integer value specified by InitMap.

In the function Bob, after calling the function InitMap once, the function MakeMap should be called exactly M times. If the function InitMap is called twice, your program is considered as Wrong Answer [15]. If the function MakeMap is called before the function InitMap is called, your program is considered as Wrong Answer [16]. If InitMap is not called when the function Bob terminates, or, the function MakeMap is not called M times, your program is considered as Wrong Answer [17]. Here, M is the integer value specified by InitMap.

If the call to the function Bob is considered Wrong Answer, your program is terminated immediately.

The sample grader reads the following data from the standard input.

• The first line contains two space separated integers This means JOI Kingdom consists of N islands, and there are M airline routes in JOI Kingdom.
• The following M lines contain information of the airline route map. The (i + 1)-th line (0 ≤ i ≤ M − 1) of the M lines contains two space separated integers A_i, B_i. They describe information of the airline route map of JOI Kingdom.

When the program terminates successfully, the sample grader writes the following information to the standard output. (The quotation mark is not written actually.)

• If your program is considered as Wrong Answer, the sample grader writes its type in the following form “Wrong Answer [1]” and terminates.
• If either of the calls to Alice and Bob are not considered as Wrong Answer, the sample grader writes “Accepted.” It also outputs the value of V.

If your program is considered as several types of Wrong Answer, the sample grader reports only one of them.

• 1 ≤ N ≤ 1 000.
• 0 ≤ M ≤ N(N − 1)/2.
• 0 ≤ A_i ≤ N − 1 (0 ≤ i ≤ M − 1).
• 0 ≤ B_i ≤ N − 1 (0 ≤ i ≤ M − 1).
• A_i ≠ B_i (0 ≤ i ≤ M − 1).
• (A_i, B_i) ≠ (A_j, B_j) and (A_i, B_i) ≠ (B_j, A_j) (0 ≤ i < j ≤ M − 1).

• In Subtask 1 or Subtask 2, if your program solves all of the test cases, you get full score.
• In Subtask 3, if your program solves all of the test cases, your score is calculated as follows. Let MaxDiff be the maximum of the difference V − N.
  • When 101 ≤ MaxDiff, your score is 0.
  • When 21 ≤ MaxDiff ≤ 100, your score is 13 + [(100 − MaxDiff)/4]. Here, [x] is the largest integer not exceeding x.
  • When 13 ≤ MaxDiff ≤ 20, your score is 33 + (20 − MaxDiff) × 3.
  • When MaxDiff ≤ 12, your score is 63.

Here is a sample input for sample grader and corresponding function calls.

4 3
0 1
0 2
0 3

In this case, the parameters given to the functions Alice(...), Bob(...) are as follows.

• dist.zip