#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 9e4 + 20;
vector<pair<int, int>> adj[maxN];
bool flag[maxN];
int distX[maxN];
int distY[maxN];
long long min_dist;
int N, M;
void bfs1(int X, int distX[]) {
for (int i = 0; i < N; i++) {
flag[i] = false;
}
deque<int> q = {X};
flag[X] = true;
distX[X] = 0;
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (auto e: adj[u]) {
int v = e.first;
if (!flag[v]) {
flag[v] = true;
distX[v] = distX[u] + 1;
q.push_back(v);
}
}
}
}
vector<pair<int, int>> bfs2(int X, int distX[], int distY[]) {
for (int i = 0; i < N; i++) {
flag[i] = false;
}
deque<int> q = {X};
flag[X] = true;
vector<pair<int, int>> tree;
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (auto e: adj[u]) {
int v = e.first;
int id = e.second;
if (distX[v] < distY[v] && !flag[v]) {
flag[v] = true;
q.push_back(v);
tree.emplace_back(v, id);
}
}
}
reverse(tree.begin(), tree.end());
return tree;
}
int solve(int X, vector<pair<int, int>> treeX, vector<pair<int, int>> treeY, int first) {
int sz = treeX.size();
int lt = 0;
int rt = sz - 1;
int res = X;
while (lt <= rt) {
int mt = (lt + rt) / 2;
vector<int> heavy(M, 1);
heavy[first] = 0;
for (auto p: treeY) {
heavy[p.second] = 0;
}
for (int i = mt + 1; i < sz; i++) {
heavy[treeX[i].second] = 0;
}
if (ask(heavy) != min_dist) {
res = treeX[mt].first;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
return res;
}
void find_pair(int _N, vector<int> U, vector<int> V, int A, int B) {
N = _N;
M = U.size();
for (int i = 0; i < M; i++) {
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
min_dist = ask(vector<int>(M, 0));
int lt = 0;
int rt = M - 1;
int first = -1;
while (lt <= rt) {
int mt = (lt + rt) / 2;
vector<int> heavy(M);
for (int i = 0; i <= mt; i++) {
heavy[i] = 1;
}
if (ask(heavy) != min_dist) {
first = mt;
rt = mt - 1;
}
else {
lt = mt + 1;
}
}
int X = U[first];
int Y = V[first];
bfs1(X, distX);
bfs1(Y, distY);
vector<pair<int, int>> treeX = bfs2(X, distX, distY);
vector<pair<int, int>> treeY = bfs2(Y, distY, distX);
answer(solve(X, treeX, treeY, first), solve(Y, treeY, treeX, first));
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2420 KB |
Output is correct |
2 |
Correct |
2 ms |
2436 KB |
Output is correct |
3 |
Correct |
1 ms |
2384 KB |
Output is correct |
4 |
Correct |
1 ms |
2424 KB |
Output is correct |
5 |
Correct |
1 ms |
2384 KB |
Output is correct |
6 |
Correct |
2 ms |
2384 KB |
Output is correct |
7 |
Correct |
2 ms |
2424 KB |
Output is correct |
8 |
Correct |
1 ms |
2420 KB |
Output is correct |
9 |
Correct |
2 ms |
2384 KB |
Output is correct |
10 |
Correct |
2 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2384 KB |
Output is correct |
12 |
Correct |
1 ms |
2424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2472 KB |
Output is correct |
2 |
Correct |
10 ms |
3372 KB |
Output is correct |
3 |
Correct |
130 ms |
10632 KB |
Output is correct |
4 |
Correct |
90 ms |
10552 KB |
Output is correct |
5 |
Correct |
88 ms |
10624 KB |
Output is correct |
6 |
Correct |
128 ms |
10592 KB |
Output is correct |
7 |
Correct |
117 ms |
10628 KB |
Output is correct |
8 |
Correct |
82 ms |
10548 KB |
Output is correct |
9 |
Correct |
74 ms |
10636 KB |
Output is correct |
10 |
Correct |
117 ms |
10632 KB |
Output is correct |
11 |
Correct |
87 ms |
9904 KB |
Output is correct |
12 |
Correct |
93 ms |
10112 KB |
Output is correct |
13 |
Correct |
93 ms |
9988 KB |
Output is correct |
14 |
Correct |
123 ms |
9916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3184 KB |
Output is correct |
2 |
Correct |
20 ms |
4136 KB |
Output is correct |
3 |
Correct |
29 ms |
4956 KB |
Output is correct |
4 |
Correct |
94 ms |
10020 KB |
Output is correct |
5 |
Correct |
62 ms |
9912 KB |
Output is correct |
6 |
Correct |
90 ms |
10020 KB |
Output is correct |
7 |
Correct |
84 ms |
9964 KB |
Output is correct |
8 |
Correct |
82 ms |
9948 KB |
Output is correct |
9 |
Correct |
117 ms |
10060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2512 KB |
Output is correct |
2 |
Correct |
12 ms |
3324 KB |
Output is correct |
3 |
Correct |
85 ms |
8608 KB |
Output is correct |
4 |
Correct |
78 ms |
10536 KB |
Output is correct |
5 |
Correct |
82 ms |
10636 KB |
Output is correct |
6 |
Correct |
70 ms |
10568 KB |
Output is correct |
7 |
Correct |
96 ms |
10648 KB |
Output is correct |
8 |
Correct |
81 ms |
10632 KB |
Output is correct |
9 |
Correct |
110 ms |
10516 KB |
Output is correct |
10 |
Correct |
101 ms |
10604 KB |
Output is correct |
11 |
Correct |
92 ms |
10028 KB |
Output is correct |
12 |
Correct |
123 ms |
9900 KB |
Output is correct |
13 |
Correct |
124 ms |
10124 KB |
Output is correct |
14 |
Correct |
91 ms |
9924 KB |
Output is correct |
15 |
Correct |
73 ms |
10600 KB |
Output is correct |
16 |
Correct |
60 ms |
10504 KB |
Output is correct |
17 |
Correct |
112 ms |
9976 KB |
Output is correct |
18 |
Correct |
82 ms |
9972 KB |
Output is correct |
19 |
Correct |
114 ms |
10652 KB |
Output is correct |
20 |
Correct |
102 ms |
9968 KB |
Output is correct |
21 |
Correct |
77 ms |
10880 KB |
Output is correct |
22 |
Correct |
62 ms |
10956 KB |
Output is correct |
23 |
Correct |
90 ms |
10792 KB |
Output is correct |
24 |
Correct |
84 ms |
10704 KB |
Output is correct |
25 |
Correct |
116 ms |
10132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
3276 KB |
Output is correct |
2 |
Correct |
14 ms |
3412 KB |
Output is correct |
3 |
Correct |
114 ms |
10848 KB |
Output is correct |
4 |
Correct |
115 ms |
11184 KB |
Output is correct |
5 |
Correct |
180 ms |
12104 KB |
Output is correct |
6 |
Correct |
171 ms |
12008 KB |
Output is correct |
7 |
Correct |
176 ms |
11912 KB |
Output is correct |
8 |
Correct |
159 ms |
11748 KB |
Output is correct |
9 |
Correct |
91 ms |
9096 KB |
Output is correct |
10 |
Correct |
109 ms |
9308 KB |
Output is correct |
11 |
Correct |
92 ms |
9784 KB |
Output is correct |
12 |
Correct |
154 ms |
11064 KB |
Output is correct |
13 |
Correct |
194 ms |
11472 KB |
Output is correct |
14 |
Correct |
145 ms |
11876 KB |
Output is correct |
15 |
Correct |
151 ms |
12120 KB |
Output is correct |
16 |
Correct |
157 ms |
9824 KB |
Output is correct |
17 |
Correct |
105 ms |
10736 KB |
Output is correct |
18 |
Correct |
96 ms |
11016 KB |
Output is correct |
19 |
Correct |
138 ms |
10860 KB |
Output is correct |
20 |
Correct |
118 ms |
11012 KB |
Output is correct |
21 |
Correct |
152 ms |
12304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
3268 KB |
Output is correct |
2 |
Correct |
17 ms |
3392 KB |
Output is correct |
3 |
Correct |
142 ms |
10600 KB |
Output is correct |
4 |
Correct |
144 ms |
10828 KB |
Output is correct |
5 |
Correct |
140 ms |
11108 KB |
Output is correct |
6 |
Correct |
137 ms |
11948 KB |
Output is correct |
7 |
Correct |
90 ms |
10984 KB |
Output is correct |
8 |
Correct |
146 ms |
10976 KB |
Output is correct |
9 |
Correct |
139 ms |
11076 KB |
Output is correct |
10 |
Correct |
173 ms |
11848 KB |
Output is correct |
11 |
Correct |
141 ms |
11776 KB |
Output is correct |
12 |
Correct |
149 ms |
12212 KB |
Output is correct |
13 |
Correct |
120 ms |
9672 KB |
Output is correct |
14 |
Correct |
158 ms |
9300 KB |
Output is correct |
15 |
Correct |
89 ms |
9676 KB |
Output is correct |
16 |
Correct |
110 ms |
9320 KB |
Output is correct |
17 |
Correct |
106 ms |
9740 KB |
Output is correct |
18 |
Correct |
112 ms |
9312 KB |
Output is correct |
19 |
Correct |
118 ms |
11048 KB |
Output is correct |
20 |
Correct |
178 ms |
11820 KB |
Output is correct |
21 |
Correct |
193 ms |
11940 KB |
Output is correct |
22 |
Correct |
176 ms |
12072 KB |
Output is correct |
23 |
Correct |
176 ms |
11820 KB |
Output is correct |
24 |
Correct |
151 ms |
12116 KB |
Output is correct |
25 |
Correct |
114 ms |
12100 KB |
Output is correct |
26 |
Correct |
181 ms |
12092 KB |
Output is correct |
27 |
Correct |
118 ms |
10888 KB |
Output is correct |
28 |
Correct |
70 ms |
10836 KB |
Output is correct |
29 |
Correct |
90 ms |
11132 KB |
Output is correct |
30 |
Correct |
118 ms |
10996 KB |
Output is correct |
31 |
Correct |
105 ms |
10868 KB |
Output is correct |
32 |
Correct |
114 ms |
10780 KB |
Output is correct |
33 |
Correct |
89 ms |
11080 KB |
Output is correct |
34 |
Correct |
98 ms |
10856 KB |
Output is correct |
35 |
Correct |
91 ms |
10848 KB |
Output is correct |
36 |
Correct |
88 ms |
10780 KB |
Output is correct |
37 |
Correct |
93 ms |
10984 KB |
Output is correct |
38 |
Correct |
74 ms |
10880 KB |
Output is correct |
39 |
Correct |
123 ms |
12512 KB |
Output is correct |
40 |
Correct |
164 ms |
12348 KB |
Output is correct |
41 |
Correct |
143 ms |
12232 KB |
Output is correct |
42 |
Correct |
167 ms |
12316 KB |
Output is correct |