33OJ
登录 注册

#P15950. [JOI Final 2026] 电压 2 / Voltage 2

    ID: 20124 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>二分交互题Special Judge分治JOI(日本)2026

[JOI Final 2026] 电压 2 / Voltage 2

Problem Description

Do you know Just Odd Inventions Co., Ltd.? This company engages in nothing but just odd inventions. We abbreviate it as JOI.

In one of JOI's laboratories, there is a complicated electric circuit. The circuit consists of NN nodes and MM thin electric resistors. The nodes are numbered 00 through N−1N - 1, and the resistors are numbered 00 through M−1M - 1. Each node can be set to one of two states: high voltage or low voltage. Resistor ii (0≤i≤M−10 \le i \le M - 1) is connected from node AiA_i to another node BiB_i. Current flows through this resistor if and only if node AiA_i is set to high voltage and node BiB_i is set to low voltage. In all other cases, no current flows through it. Also, for any two nodes, there is at most one resistor connecting them, regardless of its direction.

You are a researcher at JOI, and you are going to conduct an experiment using this circuit. The resistors in the circuit are so thin that you cannot visually determine what pairs of nodes they connect. However, there is one clue: while the voltages are being set, the temperature of the circuit rises according to the number of resistors through which current flows. Therefore, after setting the voltages, you decide to touch the circuit and read its temperature. Although you cannot measure the exact temperature of the circuit, you can perform two voltage settings and compare which one makes the circuit hotter. That is, by specifying two voltage settings, you can obtain one of the following pieces of information:

  • In the first voltage setting, the number of resistors through which current flows is larger.
  • In the two voltage settings, the number of resistors through which current flows is the same.
  • In the second voltage setting, the number of resistors through which current flows is larger.

Your goal is to repeat such temperature comparisons and determine all resistors in the circuit, that is, all ordered pairs (a,b)(a, b) such that there is a resistor from node aa to node bb. You are given in advance the number of nodes NN and the number of resistors MM. You also know that every resistor connects two distinct nodes, and that for any two nodes there is at most one resistor connecting them, regardless of direction. Under these conditions, determine the entire set of ordered pairs (a,b)(a, b) corresponding to the resistors in the circuit, from the information obtained by the temperature comparisons. Note that, depending on the structure of the circuit, it may be impossible to determine the resistors uniquely no matter what comparisons are performed or how many are performed. In that case, you must report that it is impossible to determine them uniquely.

To prevent deterioration of the resistors, you are allowed to compare temperatures at most 3000030000 times.

Incidentally, what kind of invention JOI is making with this odd circuit is top secret even within the company, and nobody except the president knows it.

Given the numbers of nodes and resistors in the circuit, write a program that determines the resistors in the circuit, or reports that this is impossible, using at most 3000030000 temperature comparisons.

Implementation Details

Your submitted program must include voltage.h\texttt{voltage.h} using the #include preprocessor directive, and must implement the following function.

bool solve(int N, int M)
  • This function is called exactly once in each execution.
  • The argument NN represents the number of nodes in the circuit, NN.
  • The argument MM represents the number of resistors in the circuit, MM.
  • This function must return false if the resistor connections cannot be uniquely determined no matter what temperature comparisons are performed or how many are performed; otherwise, it must return true.
  • If this function returns true when the resistor connections cannot be determined uniquely, your program is judged as Wrong Answer [1].
  • If this function returns false even though the circuit can be determined from temperature comparisons, your program is judged as Wrong Answer [2].

Your program may call the following functions.

int query(std::vector<int> x, std::vector<int> y)
  • By using this function, you can perform two voltage settings and compare their temperatures.
  • The argument x specifies the first voltage setting, and the argument y specifies the second voltage setting.
  • The arguments x and y must be arrays of length NN consisting of 00's and 11's.
  • If x[k]x[k] (0≤k≤N−10 \le k \le N - 1) is 11, then in the first voltage setting, node kk is set to high voltage; if x[k]x[k] is 00, then node kk is set to low voltage.
  • If y[k]y[k] (0≤k≤N−10 \le k \le N - 1) is 11, then in the second voltage setting, node kk is set to high voltage; if y[k]y[k] is 00, then node kk is set to low voltage.
  • The return value of this function is the result of comparing the temperatures of the circuit under the first and second voltage settings, and is one of −1-1, 00, or 11.
    • If the return value is −1-1, then the number of resistors through which current flows is larger in the first voltage setting than in the second.
    • If the return value is 00, then the numbers of resistors through which current flows are equal in the first and second voltage settings.
    • If the return value is 11, then the number of resistors through which current flows is larger in the second voltage setting than in the first.
  • If the length of x is not NN, your program is judged as Wrong Answer [3].
  • If x contains a value other than 00 or 11, your program is judged as Wrong Answer [4].
  • If the length of y is not NN, your program is judged as Wrong Answer [5].
  • If y contains a value other than 00 or 11, your program is judged as Wrong Answer [6].
  • You must not call this function more than 3000030000 times. If this function is called more than 3000030000 times, your program is judged as Wrong Answer [7].
void answer(int a, int b)
  • Use this function to report a resistor that you have identified.
  • The arguments a and b indicate that there is a resistor directed from node aa to node bb.
  • It must hold that 0≤a≤N−10 \le a \le N - 1 and 0≤b≤N−10 \le b \le N - 1. If this condition is not satisfied, your program is judged as Wrong Answer [8].
  • You must not call this function two or more times with the same pair (a,ba, b). If this condition is violated, your program is judged as Wrong Answer [9].
  • You must not call this function more than MM times. If this function is called more than MM times, your program is judged as Wrong Answer [10].
  • When the function solve returns true, the function answer must have been called exactly MM times. If this condition is not satisfied, your program is judged as Wrong Answer [11].
  • When the function solve returns true, for every pair (a,b)(a, b) passed as arguments to answer up to that point, there must actually exist a resistor directed from node aa to node bb. If this condition is not satisfied, your program is judged as Wrong Answer [12].

Important Notices

  • You may implement additional helper functions or declare global variables for internal use.
  • Your submitted program must not use standard input/output or any other file interaction. However, you may use standard error output for debugging.

Compilation and Execution

You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program. The sample grader is the file grader.cpp\texttt{grader.cpp}. To test your program, place the files grader.cpp\texttt{grader.cpp}, voltage.cpp\texttt{voltage.cpp}, and voltage.h\texttt{voltage.h} in the same directory, and compile them using the following command:

g++ -std=gnu++20 -O2 -o grader grader.cpp voltage.cpp

Alternatively, you can execute the compile.sh\texttt{compile.sh} file included in the archive by running:

./compile.sh

If compilation is successful, an executable file named grader\texttt{grader} will be generated.

Note that the actual grader is different from the sample grader. The sample grader is launched as a single process, which will read input data from the standard input and write the results to the standard output.

Input Format

The sample grader reads input from standard input in the following format:

N MN\ M
A0 B0A_0\ B_0
⋮\vdots
AM−1 BM−1A_{M-1}\ B_{M-1}

Output Format

The sample grader outputs the following information to standard output (quotation marks are not included in the actual output).

  • If your program is judged as one of Wrong Answer [3] – [12], the type of Wrong Answer is printed as in “Wrong Answer [5]\texttt{Wrong Answer [5]}”.
  • Otherwise, the number of calls to the function query and the return value of the function solve are printed as in “Accepted: 30 true\texttt{Accepted: 30 true}”. The sample grader, unlike the actual grader, does not judge whether the verdict should be Wrong Answer [1] or [2], that is, whether the return value of the function solvesolve is correct.

The sample grader terminates execution as soon as any of the conditions for Wrong Answer [3] – [12] is met. If multiple incorrect conditions are met, only one of them is displayed.

Hint

Notices on Grading

The actual grader is not adaptive; it has a fixed answer from the beginning of the interaction.

Example Interaction

Below is an example of input that the sample grader reads and the corresponding function calls.

Input

5 6
0 2
2 1
0 3
3 2
3 4
4 1
solve Call Return Value Function Call Return Value
solve(5, 6)\texttt{solve(5,\,6)}
query([0,0,1,1,1], [1,1,1,0,0])\texttt{query([0,0,1,1,1], [1,1,1,0,0])} -1\texttt{-1}
query([1,0,1,0,0], [0,1,0,1,0])\texttt{query([1,0,1,0,0], [0,1,0,1,0])} 0\texttt{0}
query([0,1,1,1,0], [1,1,0,1,1])\texttt{query([0,1,1,1,0], [1,1,0,1,1])} 1\texttt{1}
answer(0,2)\texttt{answer(0,2)}
answer(0,3)\texttt{answer(0,3)}
answer(2,1)\texttt{answer(2,1)}
answer(3,4)\texttt{answer(3,4)}
answer(3,2)\texttt{answer(3,2)}
answer(4,1)\texttt{answer(4,1)}
true\texttt{true}

In the first call to query, the two voltage settings and the resistors through which current flows are as follows.

  • In the first setting, nodes 00 and 11 are set to low voltage, and nodes 22, 33, and 44 are set to high voltage. At this time, current flows through resistors 11 and 55.
  • In the second setting, nodes 33 and 44 are set to low voltage, and nodes 00, 11, and 22 are set to high voltage. At this time, current flows through resistor 22.

Since the number of resistors through which current flows is larger in the first voltage setting, the return value is -1\texttt{-1}.

This sample input satisfies the constraints for subtasks 5,65,6.

Among the files available for download from the contest site: sample-01-in.txt\texttt{sample-01-in.txt} corresponds to Sample Input 11. Additionally, sample-02-in.txt\texttt{sample-02-in.txt} satisfies the constraints for all subtasks, and sample-03-in.txt\texttt{sample-03-in.txt} satisfies the constraints for subtasks 3,4,5,63,4,5,6.

Constraints

  • 2≤N≤5002 \le N \le 500.
  • 1≤M≤10001 \le M \le 1000.
  • 0≤Ai≤N−10 \le A_i \le N-1 (0≤i≤M−10 \le i \le M-1).
  • 0≤Bi≤N−10 \le B_i \le N-1 (0≤i≤M−10 \le i \le M-1).
  • Ai≠BiA_i \ne B_i (0≤i≤M−10 \le i \le M-1).
  • (Ai,Bi)≠(Aj,Bj)(A_i, B_i) \ne (A_j, B_j) and (Ai,Bi)≠(Bj,Aj)(A_i, B_i) \ne (B_j, A_j) (0≤i<j≤M−10 \le i < j \le M-1).
  • N,M,Ai,N, M, A_i, and BiB_i are integers (0≤i≤M−10 \le i \le M-1).

Subtasks

  1. (10 points) N≤100, M=N−1, Bi=Ai+1N \le 100,\ M = N-1,\ B_i = A_{i+1} (0≤i≤N−30 \le i \le N-3), and the NN values A0,A1,…,AN−2,BN−2A_0, A_1, \dots, A_{N-2}, B_{N-2} are all distinct.
  2. (12 points) M=N−1, Bi=Ai+1M = N-1,\ B_i = A_{i+1} (0≤i≤N−30 \le i \le N-3), and the NN values A0,A1,…,AN−2,BN−2A_0, A_1, \dots, A_{N-2}, B_{N-2} are all distinct.
  3. (27 points) N≤100, Ai≠AjN \le 100,\ A_i \ne A_j (0≤i<j≤M−10 \le i < j \le M-1).
  4. (18 points) Ai≠AjA_i \ne A_j (0≤i<j≤M−10 \le i < j \le M-1).
  5. (17 points) N≤100N \le 100.
  6. (16 points) No additional constraints.