#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "highway.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pll pair<long long, long long>
#define pii pair<int, int>
using namespace std;
//const int N = 2e5 + 10;
int n, m;
vector < vector <pii> > g, gr;
vector <int> h, visited;
vector <pii> par;
void dfs(int u, int p, int id_w, int height) {
h[u] = height;
par[u] = {p, id_w};
for (auto to : gr[u])
if (to.fi != p)
dfs(to.fi, u, to.se, h[u] + 1);
}
void dfs_count(int u, int p) {
visited.pb(u);
for (auto to : gr[u])
if (to.fi != p)
dfs_count(to.fi, u);
}
bool cmp(pii x, pii y) {return x.se > y.se;}
int solve_from(int x, int dist, ll val, vector <int> vertical) {
visited.clear();
dfs_count(x, -1);
h.resize(n);
par.resize(n);
dfs(x, -1, -1, 0);
vector <pii> c(visited.size());
for (int i = 0; i < visited.size(); i++)
c[i] = {visited[i], h[visited[i]]};
sort(c.begin(), c.end(), cmp);
int L = 0, R = visited.size() - 1, M;
int idc = visited.size() - 1;
vector <int> w;
while (L <= R) {
w.assign(m, 0);
for (int to : vertical)
w[to] = 1;
M = (L + R) / 2;
for (int i = 0; i <= M; i++)
if (par[c[i].fi].fi != -1)
w[par[c[i].fi].se] = 1;
ll curval = ask(w);
if (curval > val) {
idc = min(idc, M);
R = M - 1;
} else
L = M + 1;
}
return c[idc].fi;
}
void bfs_tree(int x, int y) {
queue <int> q;
q.push(x);
q.push(y);
vector <bool> vis(n, false);
vis[x] = vis[y] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto to : g[cur]) {
if (vis[to.fi])
continue;
vis[to.fi] = true;
q.push(to.fi);
// cout << cur << " " << to.fi << endl;
gr[cur].pb(to);
gr[to.fi].pb({cur, to.se});
}
}
}
void find_pair(int n1, vector <int> U, vector <int> V, int A, int B) {
n = n1;
m = U.size();
g.resize(n);
gr.resize(n);
for (int i = 0; i < m; i++) {
g[U[i]].pb({V[i], i});
g[V[i]].pb({U[i], i});
}
vector <int> w(m, 0);
ll val = ask(w);
int dist = (val / (A * 1ll));
int L = 0, R = m - 1, M, x = m;
while (L <= R) {
w.assign(m, 0);
M = (L + R) / 2;
for (int i = 0; i <= M; i++)
w[i] = 1;
ll curval = ask(w);
if (curval > val) {
x = min(x, M);
R = M - 1;
} else
L = M + 1;
}
// cout << x << " " << U[x] << " " << V[x] << endl;
// cout << x << endl;
// return;
bfs_tree(U[x], V[x]);
vector <bool> vis(m, false);
vector <int> vertical;
for (int i = 0; i < n; i++)
for (auto to : gr[i])
vis[to.se] = true;
for (int i = 0; i < m; i++)
if (!vis[i] && i != x)
vertical.pb(i);
int s = solve_from(U[x], dist, val, vertical);
int t = solve_from(V[x], dist, val, vertical);
// cout << s << " " << t << endl;
answer(s, t);
}
Compilation message
highway.cpp: In function 'int solve_from(int, int, long long int, std::vector<int>)':
highway.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < visited.size(); i++)
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
392 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
17 ms |
2048 KB |
Output is correct |
3 |
Correct |
231 ms |
15832 KB |
Output is correct |
4 |
Correct |
187 ms |
15744 KB |
Output is correct |
5 |
Correct |
251 ms |
15756 KB |
Output is correct |
6 |
Correct |
186 ms |
15812 KB |
Output is correct |
7 |
Correct |
204 ms |
15752 KB |
Output is correct |
8 |
Correct |
213 ms |
15836 KB |
Output is correct |
9 |
Correct |
197 ms |
15844 KB |
Output is correct |
10 |
Correct |
198 ms |
15808 KB |
Output is correct |
11 |
Correct |
238 ms |
15008 KB |
Output is correct |
12 |
Correct |
226 ms |
15784 KB |
Output is correct |
13 |
Correct |
224 ms |
15680 KB |
Output is correct |
14 |
Correct |
221 ms |
15656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
2296 KB |
Output is correct |
2 |
Correct |
28 ms |
4232 KB |
Output is correct |
3 |
Correct |
46 ms |
6300 KB |
Output is correct |
4 |
Correct |
141 ms |
16712 KB |
Output is correct |
5 |
Correct |
143 ms |
16928 KB |
Output is correct |
6 |
Correct |
163 ms |
17748 KB |
Output is correct |
7 |
Correct |
143 ms |
18664 KB |
Output is correct |
8 |
Correct |
141 ms |
17428 KB |
Output is correct |
9 |
Correct |
142 ms |
17644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
18 ms |
2048 KB |
Output is correct |
3 |
Correct |
153 ms |
12248 KB |
Output is correct |
4 |
Correct |
208 ms |
15764 KB |
Output is correct |
5 |
Correct |
257 ms |
15812 KB |
Output is correct |
6 |
Correct |
209 ms |
15836 KB |
Output is correct |
7 |
Correct |
210 ms |
15744 KB |
Output is correct |
8 |
Correct |
214 ms |
15724 KB |
Output is correct |
9 |
Correct |
231 ms |
15756 KB |
Output is correct |
10 |
Correct |
211 ms |
15712 KB |
Output is correct |
11 |
Correct |
214 ms |
15492 KB |
Output is correct |
12 |
Correct |
207 ms |
15728 KB |
Output is correct |
13 |
Correct |
232 ms |
15616 KB |
Output is correct |
14 |
Correct |
221 ms |
15380 KB |
Output is correct |
15 |
Correct |
200 ms |
15760 KB |
Output is correct |
16 |
Correct |
214 ms |
15784 KB |
Output is correct |
17 |
Correct |
228 ms |
15644 KB |
Output is correct |
18 |
Correct |
227 ms |
15832 KB |
Output is correct |
19 |
Correct |
208 ms |
15756 KB |
Output is correct |
20 |
Correct |
212 ms |
16236 KB |
Output is correct |
21 |
Correct |
143 ms |
16436 KB |
Output is correct |
22 |
Correct |
156 ms |
16424 KB |
Output is correct |
23 |
Correct |
192 ms |
16008 KB |
Output is correct |
24 |
Correct |
176 ms |
16032 KB |
Output is correct |
25 |
Correct |
196 ms |
18332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
2168 KB |
Output is correct |
2 |
Correct |
20 ms |
2168 KB |
Output is correct |
3 |
Correct |
233 ms |
16112 KB |
Output is correct |
4 |
Correct |
250 ms |
16436 KB |
Output is correct |
5 |
Correct |
331 ms |
17656 KB |
Output is correct |
6 |
Correct |
345 ms |
17548 KB |
Output is correct |
7 |
Correct |
328 ms |
17088 KB |
Output is correct |
8 |
Correct |
319 ms |
17240 KB |
Output is correct |
9 |
Correct |
181 ms |
10700 KB |
Output is correct |
10 |
Correct |
190 ms |
10568 KB |
Output is correct |
11 |
Correct |
185 ms |
12384 KB |
Output is correct |
12 |
Correct |
282 ms |
15208 KB |
Output is correct |
13 |
Correct |
347 ms |
16108 KB |
Output is correct |
14 |
Correct |
387 ms |
17108 KB |
Output is correct |
15 |
Correct |
375 ms |
17304 KB |
Output is correct |
16 |
Correct |
306 ms |
12076 KB |
Output is correct |
17 |
Correct |
160 ms |
16456 KB |
Output is correct |
18 |
Correct |
190 ms |
16784 KB |
Output is correct |
19 |
Correct |
185 ms |
16608 KB |
Output is correct |
20 |
Correct |
233 ms |
16684 KB |
Output is correct |
21 |
Correct |
313 ms |
17648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
2048 KB |
Output is correct |
2 |
Correct |
19 ms |
2176 KB |
Output is correct |
3 |
Correct |
319 ms |
15688 KB |
Output is correct |
4 |
Correct |
321 ms |
15960 KB |
Output is correct |
5 |
Correct |
259 ms |
16268 KB |
Output is correct |
6 |
Correct |
358 ms |
17296 KB |
Output is correct |
7 |
Correct |
267 ms |
16344 KB |
Output is correct |
8 |
Correct |
287 ms |
16316 KB |
Output is correct |
9 |
Correct |
321 ms |
16320 KB |
Output is correct |
10 |
Correct |
308 ms |
17140 KB |
Output is correct |
11 |
Correct |
302 ms |
17300 KB |
Output is correct |
12 |
Correct |
304 ms |
17324 KB |
Output is correct |
13 |
Correct |
269 ms |
12564 KB |
Output is correct |
14 |
Correct |
183 ms |
10480 KB |
Output is correct |
15 |
Correct |
200 ms |
12588 KB |
Output is correct |
16 |
Correct |
184 ms |
10480 KB |
Output is correct |
17 |
Correct |
269 ms |
12552 KB |
Output is correct |
18 |
Correct |
181 ms |
10568 KB |
Output is correct |
19 |
Correct |
274 ms |
15112 KB |
Output is correct |
20 |
Correct |
285 ms |
16336 KB |
Output is correct |
21 |
Correct |
317 ms |
16880 KB |
Output is correct |
22 |
Correct |
315 ms |
16948 KB |
Output is correct |
23 |
Correct |
339 ms |
17028 KB |
Output is correct |
24 |
Correct |
314 ms |
17056 KB |
Output is correct |
25 |
Correct |
335 ms |
17312 KB |
Output is correct |
26 |
Correct |
305 ms |
17228 KB |
Output is correct |
27 |
Correct |
165 ms |
16612 KB |
Output is correct |
28 |
Correct |
186 ms |
16608 KB |
Output is correct |
29 |
Correct |
185 ms |
17056 KB |
Output is correct |
30 |
Correct |
188 ms |
16712 KB |
Output is correct |
31 |
Correct |
176 ms |
16736 KB |
Output is correct |
32 |
Correct |
193 ms |
16504 KB |
Output is correct |
33 |
Correct |
189 ms |
17032 KB |
Output is correct |
34 |
Correct |
191 ms |
16552 KB |
Output is correct |
35 |
Correct |
191 ms |
16540 KB |
Output is correct |
36 |
Correct |
186 ms |
16828 KB |
Output is correct |
37 |
Correct |
187 ms |
17056 KB |
Output is correct |
38 |
Correct |
186 ms |
16812 KB |
Output is correct |
39 |
Correct |
298 ms |
18096 KB |
Output is correct |
40 |
Correct |
309 ms |
18048 KB |
Output is correct |
41 |
Correct |
277 ms |
17636 KB |
Output is correct |
42 |
Correct |
310 ms |
17488 KB |
Output is correct |