The IOI 2023 organizers are in big trouble! They forgot to plan the trip to Ópusztaszer for the upcoming day. But maybe it is not yet too late
There are landmarks at Ópusztaszer indexed from to . Some pairs of these landmarks are connected by bidirectional roads. Each pair of landmarks is connected by at most one road. The organizers don't know which landmarks are connected by roads.
We say that the density of the road network at Ópusztaszer is at least if every distinct landmarks have at least roads among them. In other words, for each triplet of landmarks such that , among the pairs of landmarks , and at least pairs are connected by a road.
The organizers know a positive integer such that the density of the road network is at least . Note that the value of cannot be greater than .
The organizers can make calls to the phone dispatcher at Ópusztaszer to gather information about the road connections between certain landmarks. In each call, two nonempty arrays of landmarks and must be specified. The landmarks must be pairwise distinct, that is,
 for each and such that ;
 for each and such that ;
 for each and such that and .
For each call, the dispatcher reports whether there is a road connecting a landmark from and a
landmark from . More precisely, the dispatcher iterates over all pairs and such that
and . If, for any of them, the landmarks and are connected by a road, the
dispatcher returns true
. Otherwise, the dispatcher returns false
.
A trip of length is a sequence of distinct landmarks , where for each between and , inclusive, landmark and landmark are connected by a road. A trip of length is called a longest trip if there does not exist any trip of length at least .
Your task is to help the organizers to find a longest trip at Ópusztaszer by making calls to the dispatcher.
Implementation Details
You should implement the following procedure:
std::vector<int> longest_trip(int N, int D)
 : the number of landmarks at Ópusztaszer.
 : the guaranteed minimum density of the road network.
 This procedure should return an array , representing a longest trip.
 This procedure may be called multiple times in each test case.
The above procedure can make calls to the following procedure:
bool are_connected(std::vector<int> A, std::vector<int> B)
 : a nonempty array of distinct landmarks.
 : a nonempty array of distinct landmarks.
 and should be disjoint.
 This procedure returns
true
if there is a landmark from and a landmark from connected by a road. Otherwise, it returnsfalse
.  This procedure can be called at most times in each invocation of
longest_trip
, and at most times in total.  The total length of arrays and passed to this procedure over all of its invocations cannot exceed .
The grader is not adaptive. Each submission is graded on the same set of test cases. That is, the
values of and , as well as the pairs of landmarks connected by roads, are fixed for each call of
longest_trip
within each test case.
Examples
Example 1
Consider a scenario in which , and the road connections are as shown in the following figure:
The procedure longest_trip is called in the following way:
longest_trip(5, 1)
The procedure may make calls to are_connected as follows.
Call  Pairs connected by a road  Return value 

are_connected([0], [1, 2, 4, 3]) 
and  true 
are_connected([2], [0]) 
true 

are_connected([2], [3]) 
true 

are_connected([1, 0], [4, 3]) 
none  false 
After the fourth call, it turns out that none of the pairs and is connected by a road. As the density of the network is at least , we see that from the triplet , the pair must be connected by a road. Similarly to this, landmarks and must be connected.
At this point, it can be concluded that is a trip of length , and that there does not
exist a trip of length greater than . Therefore, the procedure longest_trip
may return
.
Consider another scenario in which and the roads between the landmarks are as
shown in the following figure:
The procedure longest_trip
is called in the following way:
longest_trip(4, 1)
In this scenario, the length of a longest trip is . Therefore, after a few calls to procedure
are_connected, the procedure longest_trip
may return one of or .
Example 2
Subtask contains an additional example test case with landmarks. This test case is included in the attachment package that you can download from the contest system.
Constraints
 The sum of over all calls to
longest_trip
does not exceed in each test case.
Subtasks
 ( points)
 ( points)
 ( points) . Let denote the length of a longest trip. Procedure
longest_trip
does not have to return a trip of length . Instead, it should return a trip of length at least .  ( points)
In subtask , your score is determined based on the number of calls to procedure are_connected
over a single invocation of longest_trip
. Let be the maximum number of calls among all
invocations of longest_trip
over every test case of the subtask. Your score for this subtask is
calculated according to the following table:
Condition  Points 

If, in any of the test cases, the calls to the procedure are_connected
do not conform to the
constraints described in Implementation Details, or the array returned by longest_trip
is
incorrect, the score of your solution for that subtask will be .
Sample Grader
Let denote the number of scenarios, that is, the number of calls to longest_trip
. The sample
grader reads the input in the following format:
 line :
The descriptions of scenarios follow.
The sample grader reads the description of each scenario in the following format:
 line :
 line :
Here, each is an array of size , describing which pairs of landmarks are connected by a road. For each and such that and :
 if landmarks and are connected by a road, then the value of should be ;
 if there is no road connecting landmarks and , then the value of should be .
In each scenario, before calling longest_trip
, the sample grader checks whether the density of
the road network is at least . If this condition is not met, it prints the message Insufficient
Density
and terminates.
If the sample grader detects a protocol violation, the output of the sample grader is Protocol Violation: <MSG>
, where <MSG>
is one of the following error messages:
invalid array
: in a call toare_connected
, at least one of arrays and is empty, or
 contains an element that is not an integer between and , inclusive, or
 contains the same element at least twice.
nondisjoint arrays
: in a call toare_connected
, arrays and are not disjoint.too many calls
: the number of calls made toare_connected
exceeds over the current invocation of longest trip, or exceeds in total.too many elements
: the total number of landmarks passed toare_connected
over all calls exceeds .
Otherwise, let the elements of the array returned by longest_trip
in a scenario be
for some nonnegative . The sample grader prints three lines for this scenario
in the following format:
 line :
 line :
 line : the number of calls to
are_connected
over this scenario
Finally, the sample grader prints:
 line : the maximum number of calls to
are_connected
over all calls tolongest_trip
Attachment Package
The sample grader along with sample test cases are available here.
Comments