2258C.md (4490B)
1 Source: https://codeforces.com/problemset/problem/2258/C 2 3 C. Far Cities 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is an interactive problem. 22 23 Seferoglu lives in a small coastal city called Samsun, a city where not many people study competitive programming. Whenever an event takes place, he has to travel to far cities where he can meet his friends. Since he is tired of calculating the length of his journey exactly each time, he is just curious about the maximum distance he will ever have to travel between two cities in the worst case scenario. Your task is to help him find this distance while keeping the amount of web searches he has to make small. 24 25 There is a hidden tree$^{\text{∗}}$ with $n$ vertices. You can make queries. In one query, you choose two vertices $1 \le u, v \le n$ and an integer $0 \le d \le n$; the grader responds with $1$ if $\operatorname{dist}(u, v) \ge d$ and $0$ otherwise. Here, $\operatorname{dist}(u,v)$ denotes the distance$^{\text{†}}$ between vertices $u$ and $v$ in the tree. 26 27 Your task is to determine the diameter's length$^{\text{‡}}$ of the tree and any pair of nodes that are this distance apart. You may ask at most $3 \cdot n$ queries. 28 29 $^{\text{∗}}$A tree is a connected graph without cycles. 30 31 $^{\text{†}}$The distance between two nodes in a tree is the number of edges in the unique simple path between these nodes. 32 33 $^{\text{‡}}$The diameter's length is the largest distance between two vertices. 34 35 Input 36 37 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows. 38 39 The first line of each test case contains $n$ ($2 \le n \le 1000$), denoting the number of vertices in the tree. 40 41 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$. 42 43 Interaction 44 45 To make a query, first pick $u$, $v$ and $d$ ($1 \le u, v \le n$, $0 \le d \le n$), a pair of nodes and a constant to check the distance between them against, and output the following line (without quotes): 46 47 * "? u v d" 48 49 Afterwards, you should read one single integer ($1$ or $0$), whether $d$ was less than or equal to $\text{dist}(u, v)$ or not. 50 51 Note you may ask at most $3 \cdot n$ such queries. 52 53 Next, if your program has found an answer, it should print the following line (without quotes): 54 55 * "! u v d" 56 57 For some candidate $u$ and $v$ nodes denoting the endpoints of a diameter ($1 \le u, v \le n$) and the length of the path between them ($0 \le d \le n-1$). If there are multiple answers, any one of them may be printed. 58 59 Note that this action is not counted towards the maximum query limit. 60 61 The grader is non-adaptive. This means that the graph is fixed at the beginning and will not change based on your interactions. 62 63 After printing each query do not forget to output the end of line and flush$^{\text{∗}}$ the output. Otherwise, you will get Idleness limit exceeded verdict. 64 65 If, at any interaction step, you read $-1$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream. 66 67 Hacks 68 69 To hack, use the following format: 70 71 The first line contains the number of test cases $t$ ($1 \le t \le 500$). 72 73 The first line of each test case contains $n$ ($2 \le n \le 1000$), denoting the number of vertices in the tree. 74 75 The next $n-1$ lines of each test case contain two integers each $u_i, v_i$ ($1 \le u_i, v_i \le n$), denoting the edges of the tree. 76 77 $^{\text{∗}}$To flush, use: 78 79 * fflush(stdout) or cout.flush() in C++; 80 * sys.stdout.flush() in Python; 81 * see the documentation for other languages. 82 83 Example 84 85 Input 86 87 ``` 88 3 89 90 4 91 92 1 93 94 0 95 96 0 97 98 0 99 100 2 101 102 4 103 104 1 105 106 1 107 108 1 109 110 1 111 112 0 113 114 0 115 116 0 117 118 0 119 ``` 120 121 Output 122 123 ``` 124 ? 1 2 1 125 126 ? 1 2 2 127 128 ? 2 3 2 129 130 ? 3 4 2 131 132 ! 1 4 3 133 134 ! 1 2 1 135 136 ? 1 2 1 137 138 ? 1 3 1 139 140 ? 1 4 1 141 142 ? 3 4 2 143 144 ? 3 4 3 145 146 ? 1 2 2 147 148 ? 1 3 2 149 150 ? 1 4 2 151 152 ! 4 2 2 153 ``` 154 155 Note 156 157 The hidden graph in the first test case is $(1,2), (2,3), (3,4)$. 158 159 The hidden graph in the second test case is $(1,2)$. 160 161 The hidden graph in the third test case is $(1,2), (1,3), (1,4)$. 162 163 In the third test case, the answer "! 3 4 2" is also correct. 164 165 | | | | | 166 | --- | --- | --- | --- | 167 | | | | | 168 | The tree of the first testcase | The tree of the second testcase | The tree of the third testcase |