제출 #766637

#제출 시각아이디문제언어결과실행 시간메모리
766637radoslav11통행료 (IOI18_highway)C++17
51 / 100
155 ms11128 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; } 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 int cross_edge = cross_edges[found]; tie(dist, tree_edges, cross_edges) = bfs(N, U.size(), adj, {U[cross_edge], V[cross_edge]}); tree_edges.push_back(cross_edge); } 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; } int root = -1; for(int i = 0; i < N; i++) { if(main_edge[i] == -1) { root = i; } } vector<int> order_s(N); iota(order_s.begin(), order_s.end(), 0); sort(order_s.begin(), order_s.end(), [&](int i, int j) { return dist[i] > dist[j]; }); int s = find_first( main_edge, order_s, 0, (int)order_s.size() - 1, U.size(), dist_heavy ); if(s == -1) { s = root; } tie(dist, tree_edges, cross_edges) = bfs(N, U.size(), adj, {s}); vector<int> order_t(N); iota(order_t.begin(), order_t.end(), 0); sort(order_t.begin(), order_t.end(), [&](int u, int v) { return dist[u] > dist[v]; }); main_edge.assign(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; } int t = find_first( main_edge, order_t, 0, (int)order_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...