oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

navigation Communication , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

navigation.html

Anna is a resident of the IOI islands and has invited Bruno to visit. The N islands in the IOI islands are numbered from 1 to N. There are N - 1 bridges between the IOI islands which are numbered from 0 to N - 2. The ith bridge connects islands Ai and Bi. It is possible to move from each island to all other islands using only the bridges. Anna lives at island T, but Bruno does not know the number of the island at which Anna lives.

To help Bruno, Anna is able to place one flag at each of the N islands. Each flag can have one integer written on it. Anna does not know which island Bruno will arrive at.

Bruno has arrived on island S by boat. When Bruno arrives, he is given the following information:

  • The island number of the island he arrived at, S, and the integer written on the flag at S.
  • The island numbers of the islands that S has bridges to, along with the integers written on the flags at those islands.

Bruno must move from S to T on the path that uses the smallest possible number of bridges. Given only the information above, Bruno must either determine that he is at island T, or determine the correct island to proceed next to in order to reach T using the smallest number of bridges.

Anna, being a resident, knows how the IOI islands and the bridges between them are laid out. She must determine the integers to write on the flags at each island. Bruno must be able to navigate to T from any island he arrives at, using only the information given to him and still crossing the smallest possible number of bridges.

Implementation Details

You should write two files, Anna.cpp and Bruno.cpp.

The first file Anna.cpp must include Annalib.h and implement the following functions:

  • void Anna(int K, int N, int T, int A[], int B[])

    This function will be called once only.

    • Parameter K is the subtask number.
    • Parameter N is the number of islands in the IOI islands.
    • Parameter T is the island number of Anna's home island.
    • Parameters A and B are arrays of length N - 1. A[i] and B[i] represent the fact that bridge i connects islands A[i] and B[i].

You must call the following function to set the integers to be written on the flags:

  • void Flag(int I, int V)
    • Parameter I is the island number where this flag is to be placed.
    • Parameter V is the number to be written on the flag.

The calls to Flag must satisfy the following constraints:

  • I must be greater than or equal to 1 and less than or equal to N. If this constraint is not satisfied, the message "Wrong Answer [1]" will be shown.
  • Flag must not be called more than once with the same value of I. If this constraint is not satisfied, the message "Wrong Answer [2]" will be shown.
  • V must be greater than or equal to 0 and less than or equal to N. If this constraint is not satisfied, the message "Wrong Answer [3]" will be shown.
  • Flag must be called exactly N times. If this constraint is not satisfied, the message "Wrong Answer [4]" will be shown.

If any call to Flag is determined to be incorrect, the program will terminate.

The second file Bruno.cpp must include Brunolib.h and implement the following functions:

  • void Bruno(int K, int S, int F, int L, int P[], int Q[])

    This function will be called once, after Anna is called.

    • Parameter K is the subtask number.
    • Parameter S is the island number of the island Bruno arrived at.
    • Parameter F is the integer on the flag at island S.
    • Parameter L is the number of bridges connected to island S.
    • Parameter P and Q are arrays of length L. P contains the island numbers of the islands on the other side of the L bridges. Q[j] is the integer written on the flag at island P[j] (0 ≤ j ≤ L - 1).

After determining the correct island Bruno should move to or that the island Bruno is on is Anna's home island, you must call the following function to indicate the answer:

  • void Answer(int X)

    Parameter X is your answer. If the island Bruno has arrived at, S, is Anna's home island, T, X must be T. Otherwise, X must be the next island Bruno should move to from S.

    The call the Answer must satisfy the following constraints:

    • X must either be S or one of the L elements of P. If this constraint is not satisfied, the message "Wrong Answer [5]" will be shown.
    • Answer must not be called more than once. If this constraint is not satisfied, the message "Wrong Answer [6]" will be shown.
    • Answer must be called. If this constraint is not satisfied, the message "Wrong Answer [7]" will be shown.
    • If island S is Anna's home island, and X is not T, the message "Wrong Answer [8]" will be shown.
    • If island S is not Anna's home island, and X is not the correct next island Bruno should move to, the message "Wrong Answer [9]" will be shown.

    After Bruno has been called, the program will determine the correctness of your answer and terminate.

You are free to declare global variables or other functions to aid in your implementation. However, in order to avoid interference when compiling with the sample grader, you should declare all global variables static. It is not possible to share data between the two programs as they are graded separately during evaluation. You are not allowed to read or print from/to standard input/output within your program.

Compiling with the Sample Grader

A sample grader is provided to aid you in writing your program. To compile the grader, run the following command:

g++ std=c++11 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Sample Grader Input

The sample grader reads from standard input.

  • On the first line, there are 4 integers, N, S, T and K. This means there are N islands in the IOI islands, Bruno arrives at island S and Anna lives on island T. In addition, the subtask number is K.
  • On the (i + 1)th line of the next N - 1 lines (0 ≤ i ≤ N - 2), there are two integers, Ai and Bi. This means bridge i connects islands Ai and Bi.
  • On the next line, there is one integer Y. This is the correct answer. If Answer was called with X = Y, your answer will be judged as correct and wrong otherwise.

Sample Grader Output

The sample grader prints to standard output.

  • If your answer was correct, the sample grader will print the largest value of V in any call to Flag. For example, if the largest value of V used in any call to Flag is 2, the sample grader will print "Accepted : V_max = 2".
  • If your answer was wrong, the sample grader will print the error message, for example "Wrong Answer [1]".

Constraints

All test cases satisfy the following constraints.

  • 2 ≤ N ≤ 100 000.
  • 1 ≤ S ≤ N.
  • 1 ≤ T ≤ N.
  • 1 ≤ Ai ≤ N (0 ≤ i ≤ N - 2).
  • 1 ≤ Bi ≤ N (0 ≤ i ≤ N - 2).
  • 1 ≤ K ≤ 4.
  • It is possible to move to all other IOI islands from any IOI island using only the bridges given.

Subtasks

Subtask 1 (10 points):

  • K = 1 is satisfied.

Subtask 2 (15 points):

  • K = 2 is satisfied.
  • Flag must be called with parameter V greater than or equal to 0 and less than or equal to 2.

Subtask 3 (20 points):

  • K = 3 is satisfied.
  • Flag must be called with parameter V either 0 or 1.
  • There are no IOI islands which are connected to only two other IOI islands directly by bridges.
  • S ≠ T is satisfied.

Subtask 4 (55 points):

  • K = 4 is satisfied.
  • Flag must be called with parameter V either 0 or 1.

Sample Input 1

5 3 2 1
1 3
3 2
3 4
4 5
2

Sample Exchange 1

AnnaBruno
Anna(...)
Flag(1, 1)
Flag(2, 1)
Flag(3, 0)
Flag(4, 0)
Flag(5, 1)
Bruno(...)
Answer(2)

The sample calls to Flag shown here do not necessarily have any meaning. The parameters supplied to Anna and Bruno are shown as follows:

ParameterAnna(...)
K1
N5
T2
A{1, 3, 3, 4}
B{3, 2, 4, 5}

ParameterBruno(...)
K1
S3
F0
P{2, 1, 4}
Q{1, 1, 0}

Tags

JOI 2014/2015

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110251s256MBMinimum
215271s256MBMinimum
320321s256MBMinimum
455411s256MBMinimum
5011s256MBMinimum

Attachments

Attachment Filesize Last Updated
Bruno.cpp171B21 Mar 2015, 17:51:22
Anna.cpp207B22 Mar 2015, 08:40:42
sample-in-01.txt26B15 Mar 2015, 19:18:46
grader.cpp2.8KB22 Mar 2015, 08:40:42
Bruno.h58B19 Mar 2015, 07:24:16
Brunolib.h20B19 Mar 2015, 07:24:16
Annalib.h25B19 Mar 2015, 07:24:16
Anna.h50B19 Mar 2015, 07:24:16

Judge Compile Command

g++-8 before.cpp Anna.cpp -o navigation_before -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512
g++-8 after.cpp Bruno.cpp -o navigation_after -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.