This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
tuple<vector<int>, vector<int>, vector<int>> bfs(
int N, int M, vector<vector<pair<int, int>>> &adj, vector<int> srcs
) {
vector<int> dist(N, -1);
queue<int> q;
for(int u: srcs) {
dist[u] = 0;
q.push(u);
}
vector<int> tree_edges;
vector<int> cross_edges_mask(M, true);
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto [v, i]: adj[u]) {
if(dist[v] == -1) {
dist[v] = dist[u] + 1;
cross_edges_mask[i] = false;
tree_edges.push_back(i);
q.push(v);
}
}
}
vector<int> cross_edges;
for(int i = 0; i < M; i++) {
if(cross_edges_mask[i]) {
cross_edges.push_back(i);
}
}
return {dist, tree_edges, cross_edges};
}
int find_first(
vector<int> edges, vector<int> order, int l, int r, int m,
int64_t dist_heavy
) {
int found = -1, start = l;
while(l <= r) {
int mid = (l + r) >> 1;
vector<int> mask(m, 1);
for(int i = start; i <= mid; i++) {
if(edges[order[i]] != -1) {
mask[edges[order[i]]] = 0;
}
}
if(ask(mask) < dist_heavy) {
r = mid - 1;
found = order[mid];
} else {
l = mid + 1;
}
}
return found;
}
pair<int, int> solve(
vector<int> &main_edge, vector<int> &order, int l, int r, int m,
int64_t dist_heavy, int64_t dist_light
) {
if(l == r) {
uint32_t x = 329843;
while(true) {
x *= x;
}
// assert(false);
}
int mid = (l + r) >> 1;
vector<int> mask(m, 1);
for(int i = l; i <= mid; i++) {
if(main_edge[order[i]] != -1) {
mask[main_edge[order[i]]] = 0;
}
}
// cout << endl;
// for(int x: mask) {
// cout << x;
// }
// cout << endl;
int64_t dist_l = ask(mask);
// cout << "here: " << l << " " << r << endl;
// cout << "dist_l: " << dist_l << endl;
// cout << "dist_heavy: " << dist_heavy << endl;
// cout << "dist_light: " << dist_light << endl;
if(dist_l == dist_light) {
return solve(main_edge, order, l, mid, m, dist_heavy, dist_light);
} else if(dist_l == dist_heavy) {
return solve(main_edge, order, mid + 1, r, m, dist_heavy, dist_light);
} else {
return {l, r};
}
}
void pre_post_order(
vector<vector<pair<int, int>>> &adj, int u, vector<int> &perm, int par = -1
) {
perm.push_back(u);
for(auto [v, i]: adj[u]) {
if(v != par) {
pre_post_order(adj, v, perm, u);
}
}
perm.push_back(u);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
vector<vector<pair<int, int>>> adj;
adj.assign(N, {});
for(int i = 0; i < (int)U.size(); i++) {
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
vector<int> dist, tree_edges, cross_edges;
tie(dist, tree_edges, cross_edges) = bfs(N, U.size(), adj, {0});
// 1 query
int64_t dist_heavy = ask(vector<int>(U.size(), 1));
// ceil(log2(M - N)) queries. Worst case 16 queries
vector<int> order(cross_edges.size());
iota(order.begin(), order.end(), 0);
int found = find_first(
cross_edges, order, 0, (int)cross_edges.size() - 1, U.size(), dist_heavy
);
if(found != -1) {
// reroot needed to guarantee that shortest path is on bfs tree
tie(dist, tree_edges, cross_edges) =
bfs(N, U.size(), adj,
{U[cross_edges[found]], V[cross_edges[found]]});
tree_edges.push_back(found);
}
// 2 * ceil(log2(N) - 1) + 1 queries.
// Worst case 33 queries
vector<int> main_edge(N, -1);
for(auto i: tree_edges) {
int u = U[i], v = V[i];
if(dist[u] > dist[v]) {
swap(u, v);
}
main_edge[v] = i;
}
// for(int i = 0; i < N; i++) {
// cout << main_edge[i] << " ";
// }
// cout << endl;
int root = -1;
for(int i = 0; i < N; i++) {
if(main_edge[i] == -1) {
root = i;
}
}
vector<int> perm;
pre_post_order(adj, root, perm);
// cout << "perm: ";
// for(int i = 0; i < (int)perm.size(); i++) {
// cout << perm[i] << " ";
// }
// cout << endl;
int64_t dist_light = (dist_heavy / B) * A;
auto [l, r] = solve(
main_edge, perm, 0, (int)perm.size() - 1, U.size(), dist_heavy,
dist_light
);
int mid = (l + r) >> 1;
int max_depth_s = 0, max_depth_t = 0;
vector<int> mask_s(N, 0);
for(int i = l; i <= mid; i++) {
mask_s[perm[i]] = 1;
}
vector<int> search_list_s;
for(int i = 0; i < N; i++) {
if(mask_s[i] == 1) {
search_list_s.push_back(i);
max_depth_s = max(max_depth_s, dist[i]);
}
}
vector<int> search_list_t;
vector<int> mask_t(N, 0);
for(int i = mid + 1; i <= r; i++) {
mask_t[perm[i]] = 1;
}
for(int i = 0; i < N; i++) {
if(mask_t[i] == 1) {
search_list_t.push_back(i);
max_depth_t = max(max_depth_t, dist[i]);
}
}
if(max_depth_s < max_depth_t) {
swap(search_list_s, search_list_t);
}
sort(search_list_s.begin(), search_list_s.end(), [&](int u, int v) {
return dist[u] > dist[v];
});
int s = find_first(
main_edge, search_list_s, 0, (int)search_list_s.size() - 1, U.size(),
dist_heavy
);
assert(s != -1);
if(dist[s] * 1ll * B >= dist_heavy) {
main_edge.assign(main_edge.size(), -1);
for(auto i: tree_edges) {
int u = U[i], v = V[i];
if(dist[u] < dist[v]) {
swap(u, v);
}
main_edge[v] = i;
}
sort(search_list_t.begin(), search_list_t.end(), [&](int u, int v) {
return dist[u] < dist[v];
});
} else {
sort(search_list_t.begin(), search_list_t.end(), [&](int u, int v) {
return dist[u] > dist[v];
});
}
// for(int i = 0; i < (int)search_list_t.size(); i++) {
// cout << search_list_t[i] << " ";
// }
// cout << endl;
int t = find_first(
main_edge, search_list_t, 0, (int)search_list_t.size() - 1, U.size(),
dist_heavy
);
// cout << s << " " << t << endl;
if(s == -1) {
s = root;
}
if(t == -1) {
t = root;
}
answer(s, t);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |