#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int mxN = 90000;
int n, m, mn;
vector<pii> adj[mxN];
int qry(vector<int> &edges) {
vector<int> w(m);
for (int i: edges) w[i] = 1;
return ask(w);
}
int bsearch(vector<int> edges, vector<int> extras){
int lo = 0, hi = edges.size(), mid;
while (hi != lo) {
mid = lo+hi>>1;
vector<int> q = extras;
q.insert(q.end(), edges.begin(), edges.begin()+mid+1);
if (qry(q) != mn) hi = mid;
else lo = mid+1;
}
return lo;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N;
m = U.size();
for (int i = 0; i < m; ++i) {
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
vector<int> all(m);
iota(all.begin(), all.end(), 0);
mn = ask(vector<int>(m));
int fst = bsearch(all, {});
queue<int> q;
vector<int> seen(n), edge_in_tree(m), node_in_subtree(n), tree_edges, psubtree, ch(m);
q.push(U[fst]);
seen[U[fst]] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (pii e: adj[u]) if (e.second >= fst && !seen[e.first]) {
seen[e.first] = 1;
q.push(e.first);
if (node_in_subtree[u] || e.first == V[fst]) {
node_in_subtree[e.first] = 1;
psubtree.push_back(e.second);
} else {
tree_edges.push_back(e.second);
}
edge_in_tree[e.second] = 1;
ch[e.second] = e.first;
}
}
vector<int> extras;
for (int i = 0; i < m; ++i) if (!edge_in_tree[i]) extras.push_back(i);
reverse(psubtree.begin(), psubtree.end());
reverse(tree_edges.begin(), tree_edges.end());
int res = bsearch(tree_edges, extras);
answer(ch[psubtree[bsearch(psubtree, extras)]], res == tree_edges.size() ? U[fst] : ch[tree_edges[res]]);
}
Compilation message
highway.cpp: In function 'int bsearch(std::vector<int>, std::vector<int>)':
highway.cpp:19:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
19 | mid = lo+hi>>1;
| ~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:63:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | answer(ch[psubtree[bsearch(psubtree, extras)]], res == tree_edges.size() ? U[fst] : ch[tree_edges[res]]);
| ~~~~^~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2376 KB |
Output is correct |
2 |
Correct |
2 ms |
2412 KB |
Output is correct |
3 |
Correct |
2 ms |
2376 KB |
Output is correct |
4 |
Correct |
2 ms |
2376 KB |
Output is correct |
5 |
Correct |
2 ms |
2376 KB |
Output is correct |
6 |
Correct |
2 ms |
2376 KB |
Output is correct |
7 |
Correct |
2 ms |
2408 KB |
Output is correct |
8 |
Correct |
2 ms |
2376 KB |
Output is correct |
9 |
Correct |
2 ms |
2412 KB |
Output is correct |
10 |
Correct |
2 ms |
2376 KB |
Output is correct |
11 |
Correct |
2 ms |
2376 KB |
Output is correct |
12 |
Correct |
2 ms |
2412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2464 KB |
Output is correct |
2 |
Correct |
20 ms |
3240 KB |
Output is correct |
3 |
Correct |
145 ms |
10516 KB |
Output is correct |
4 |
Correct |
192 ms |
10416 KB |
Output is correct |
5 |
Correct |
143 ms |
10340 KB |
Output is correct |
6 |
Correct |
135 ms |
10608 KB |
Output is correct |
7 |
Correct |
169 ms |
10652 KB |
Output is correct |
8 |
Correct |
141 ms |
10692 KB |
Output is correct |
9 |
Correct |
134 ms |
10768 KB |
Output is correct |
10 |
Correct |
158 ms |
10372 KB |
Output is correct |
11 |
Correct |
162 ms |
10428 KB |
Output is correct |
12 |
Correct |
144 ms |
9960 KB |
Output is correct |
13 |
Correct |
181 ms |
9752 KB |
Output is correct |
14 |
Correct |
187 ms |
9744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
3284 KB |
Output is correct |
2 |
Correct |
25 ms |
4084 KB |
Output is correct |
3 |
Correct |
52 ms |
5324 KB |
Output is correct |
4 |
Correct |
148 ms |
10020 KB |
Output is correct |
5 |
Correct |
142 ms |
10064 KB |
Output is correct |
6 |
Correct |
111 ms |
9956 KB |
Output is correct |
7 |
Correct |
154 ms |
10216 KB |
Output is correct |
8 |
Correct |
125 ms |
9840 KB |
Output is correct |
9 |
Correct |
152 ms |
10112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2376 KB |
Output is correct |
2 |
Correct |
20 ms |
3264 KB |
Output is correct |
3 |
Correct |
101 ms |
9008 KB |
Output is correct |
4 |
Correct |
132 ms |
10516 KB |
Output is correct |
5 |
Correct |
114 ms |
10832 KB |
Output is correct |
6 |
Correct |
121 ms |
10740 KB |
Output is correct |
7 |
Correct |
179 ms |
10756 KB |
Output is correct |
8 |
Correct |
119 ms |
10760 KB |
Output is correct |
9 |
Correct |
185 ms |
10376 KB |
Output is correct |
10 |
Correct |
168 ms |
10688 KB |
Output is correct |
11 |
Correct |
231 ms |
10008 KB |
Output is correct |
12 |
Correct |
194 ms |
9792 KB |
Output is correct |
13 |
Correct |
160 ms |
9872 KB |
Output is correct |
14 |
Correct |
142 ms |
10264 KB |
Output is correct |
15 |
Correct |
162 ms |
10744 KB |
Output is correct |
16 |
Correct |
110 ms |
10700 KB |
Output is correct |
17 |
Correct |
186 ms |
9848 KB |
Output is correct |
18 |
Correct |
251 ms |
9780 KB |
Output is correct |
19 |
Correct |
117 ms |
10744 KB |
Output is correct |
20 |
Correct |
176 ms |
10616 KB |
Output is correct |
21 |
Correct |
109 ms |
11012 KB |
Output is correct |
22 |
Correct |
144 ms |
11004 KB |
Output is correct |
23 |
Correct |
170 ms |
10516 KB |
Output is correct |
24 |
Correct |
133 ms |
10340 KB |
Output is correct |
25 |
Correct |
140 ms |
9776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
3336 KB |
Output is correct |
2 |
Correct |
17 ms |
3428 KB |
Output is correct |
3 |
Correct |
200 ms |
10932 KB |
Output is correct |
4 |
Correct |
177 ms |
11864 KB |
Output is correct |
5 |
Correct |
291 ms |
13592 KB |
Output is correct |
6 |
Correct |
282 ms |
13252 KB |
Output is correct |
7 |
Correct |
282 ms |
13088 KB |
Output is correct |
8 |
Correct |
231 ms |
13424 KB |
Output is correct |
9 |
Correct |
168 ms |
11692 KB |
Output is correct |
10 |
Correct |
170 ms |
12160 KB |
Output is correct |
11 |
Correct |
245 ms |
12252 KB |
Output is correct |
12 |
Correct |
272 ms |
12848 KB |
Output is correct |
13 |
Correct |
352 ms |
13440 KB |
Output is correct |
14 |
Correct |
283 ms |
13208 KB |
Output is correct |
15 |
Correct |
281 ms |
13284 KB |
Output is correct |
16 |
Correct |
245 ms |
12484 KB |
Output is correct |
17 |
Correct |
169 ms |
10884 KB |
Output is correct |
18 |
Correct |
157 ms |
11160 KB |
Output is correct |
19 |
Correct |
157 ms |
10732 KB |
Output is correct |
20 |
Correct |
179 ms |
11180 KB |
Output is correct |
21 |
Correct |
225 ms |
13352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
3256 KB |
Output is correct |
2 |
Correct |
19 ms |
3392 KB |
Output is correct |
3 |
Correct |
181 ms |
10980 KB |
Output is correct |
4 |
Correct |
183 ms |
11240 KB |
Output is correct |
5 |
Correct |
258 ms |
11596 KB |
Output is correct |
6 |
Correct |
244 ms |
13420 KB |
Output is correct |
7 |
Correct |
196 ms |
11128 KB |
Output is correct |
8 |
Correct |
228 ms |
11412 KB |
Output is correct |
9 |
Correct |
238 ms |
11864 KB |
Output is correct |
10 |
Correct |
237 ms |
13352 KB |
Output is correct |
11 |
Correct |
277 ms |
13248 KB |
Output is correct |
12 |
Correct |
269 ms |
13448 KB |
Output is correct |
13 |
Correct |
213 ms |
12476 KB |
Output is correct |
14 |
Correct |
177 ms |
12164 KB |
Output is correct |
15 |
Correct |
243 ms |
12288 KB |
Output is correct |
16 |
Correct |
196 ms |
12208 KB |
Output is correct |
17 |
Correct |
243 ms |
12124 KB |
Output is correct |
18 |
Correct |
246 ms |
12436 KB |
Output is correct |
19 |
Correct |
298 ms |
13108 KB |
Output is correct |
20 |
Correct |
214 ms |
13324 KB |
Output is correct |
21 |
Correct |
249 ms |
13224 KB |
Output is correct |
22 |
Correct |
290 ms |
13268 KB |
Output is correct |
23 |
Correct |
235 ms |
13068 KB |
Output is correct |
24 |
Correct |
285 ms |
13260 KB |
Output is correct |
25 |
Correct |
230 ms |
13312 KB |
Output is correct |
26 |
Correct |
227 ms |
13324 KB |
Output is correct |
27 |
Correct |
147 ms |
11340 KB |
Output is correct |
28 |
Correct |
142 ms |
10868 KB |
Output is correct |
29 |
Correct |
168 ms |
11244 KB |
Output is correct |
30 |
Correct |
134 ms |
10876 KB |
Output is correct |
31 |
Correct |
137 ms |
11056 KB |
Output is correct |
32 |
Correct |
181 ms |
10744 KB |
Output is correct |
33 |
Correct |
130 ms |
10860 KB |
Output is correct |
34 |
Correct |
150 ms |
10972 KB |
Output is correct |
35 |
Correct |
174 ms |
10792 KB |
Output is correct |
36 |
Correct |
169 ms |
10712 KB |
Output is correct |
37 |
Correct |
148 ms |
11132 KB |
Output is correct |
38 |
Correct |
129 ms |
10948 KB |
Output is correct |
39 |
Correct |
273 ms |
13692 KB |
Output is correct |
40 |
Correct |
269 ms |
13532 KB |
Output is correct |
41 |
Correct |
241 ms |
13368 KB |
Output is correct |
42 |
Correct |
294 ms |
13180 KB |
Output is correct |