Submission #766625

#TimeUsernameProblemLanguageResultExecution timeMemory
766625radoslav11Highway Tolls (IOI18_highway)C++17
0 / 100
181 ms262144 KiB
#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) { return {l, l}; } 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 // cout << U[cross_edges[found]] << " " << V[cross_edges[found]] << endl; 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); tie(dist, tree_edges, cross_edges) = bfs(N, U.size(), adj, {s}); sort(search_list_t.begin(), search_list_t.end(), [&](int u, int v) { return dist[u] > dist[v]; }); int t = find_first( main_edge, search_list_t, 0, (int)search_list_t.size() - 1, U.size(), dist_heavy ); answer(s, t); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...