Parallel Binary Search

Resources

Solution - New Roads Queries

Let's think how to binary search a single query. It's clear that we can use DSU with linear search, but also we can do binary search with DSU in $O(N \cdot \log_2{N})$.

Now let's use parallel binary search: Sweep through the array of edges and union them in the DSU, whenevery you find a query its median = $i$, if the two nodes where connected, it means shrink to left, otherwise shrink to right.

You need to do the sweep $O(\log_2{N})$ times, so you know the exact time the nodes where connected. And you need to sort the queries by median before every sweep thats $O(Q \cdot \log_2{Q})$ And $O(\alpha{N})$ for the DSU

Total Complexity: $O((N + Q) \cdot \log_2{N}^2 \cdot \alpha{N})$

Implementation - New Roads Queries

Copy
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5 + 1;

int n, m, q;
vector<pii> edges;

Problems