# PROBLEM LINK:

Practice

Div-2 Contest

Div-1 Contest

* Author:* Sawarnik Kaushal

*Felipe Mota*

**Tester:***Sawarnik Kaushal*

**Editorialist:**# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Segment Tree, Coordinate Compression

# PROBLEM:

You are given an unweighted directed graph whose edges are given by:

- For each i, where 1 \le i \le M, and for each pair of vertices u \in [A_i, B_i], v \in [C_i, D_i], there is an edge from u to v.

Find the shortest distance between vertices X and Y.

# QUICK EXPLANATION:

- First, we compress all the vertices given in the input, so that the number of vertices becomes O(M).
- Build a graph as shown in the figure below, of size equal to the number of compressed vertices. The tree edges are weighted 0. Then for each valid i, decompose [a_i, b_i] into subsegments in the
*lower half*and draw an edge from each of them to each subsegment of [c_i, d_i] in the*upper half*. All these edges should be of weight 1. In this way, the graph consists of O(M\log^2 M) edges. Now, we can find the answer by running 0-1 BFS from source [x, x], and finding the distance to [y, y]. This solution takes O(M\log^2 M) time. - Instead of drawing an edge from each subsegment of [a_i, b_i] to each of [c_i, d_i], we can define an extra vertex v_i and draw an edge from each subsegment of [a_i, b_i] to v_i, followed by an edge from v_i to each subsegment of [c_i, d_i]. The graph now consists of a total of O(M\log M) edges. We can then run 0-1 BFS as before, but divide by 2 to get the final answer. Thus, the problem is solved in O(M\log M) time.

# EXPLANATION:

Firstly, we can compress the input so that instead of dealing with N vertices, which can be upto 10^9, we only need to deal with O(M) vertices in our graph, as there are only 4M + 2 vertices to compress. Let us represent the number of vertices after compression to be K.

**Motivation**

We can start by naively building the graph as given in the problem, followed by a BFS. The problem with this approach is that for each valid i, we require O(M^2) edges to be added to the graph in the worst case. Clearly, we need a structure which can represent that same information with far fewer edges. We can recognize that a segment tree is well-suited for such a role. For instance, let us build a segment tree of size K. Then for each valid i, we can decompose [a_i, b_i] into O(\log K) subsegments of the segment tree, and draw an edge from all those subsegments to all subsegments of [c_i, d_i]. After some experimentation with similar kind of structures, we can realize that the following graph works for us.

**Solution**

Figure: The graph for K = 5. Tree edges of weight 0 are shown in blue. For an example, edges of weight 1 from [4, 5] to [2, 5] are shown in green.

Let us construct this graph, i.e. the two segment trees of size K joined together as shown in the figure. We initially assign all the tree edges weight 0. Now, we start iterating over each valid i. As we do in any segment tree, we can partition every segment [a, b] into O(\log K) subsegments of the segment tree. Thus, for every [a_i, b_i] we draw an edge from each of its subsegments in the *lower half* to each subsegment of [c_i, d_i] in the *upper half*. We draw these edges with weight 1. So why does this graph work?

We show that if there exists an edge from vertex p to q in the original graph, then and only then there exists a path of distance 1 from segment [p, p] to [q, q] in our constructed graph. Note that if there is an edge from p to q, there must be an i such that p \in [a_i, b_i] and q \in [c_i, d_i]. Thus, there must be a subsegment of [a_i, b_i] in the segment tree which includes p, let us call it [a'_i, b'_i], and a subsegment of [c_i, d_i] including q, which we can call [c'_i, d'_i].

It is easy to see that all segments in a segment tree that include p, lie on the path from [p, p] to the root. Thus, we can move downwards from [p, p] in our graph and reach [a'_i, b'_i] in the lower half of the graph. Further, as we had drawn an edge from each subsegment of [a_i, b_i] to each subsegment of [c_i, d_i], there exists an edge from [a'_i, b'_i] in the lower half to [c'_i, d'_i] to the upper half. So we can move to [c'_i, d'_i] and from there on we can move downwards in the tree until we reach [q, q]. Thus, we have shown that a path exists from [p, p] to [q, q]. Also, notice that we used exactly 1 unit of distance in doing so. The only-if part of the proof is very similar.

Hence, any path from x to y of length l in our original graph corresponds to a path from [x, x] to [y, y] of the same distance l in our constructed graph, and vice versa. So how can we find the shortest path from [x, x] to [y, y]? The simplest way is to use 0-1 BFS with source vertex [x, x], which is possible since all our edges are of weight 0 or 1. Alternatively, we can use Dijkstraâ€™s but that will result in an extra log factor in the time complexity.

**Time complexity**

Remember that the compression phase took O(M\log M) time. Now, as building a segment tree of size K requires O(K) edges our initial graph consisted of O(K) edges as well, or equivalently O(M) edges. Then, for each i we divided the segments [a_i, b_i] and [c_i, d_i] into their O(\log M) subsegments, and we defined an edge from each subsegment of [a_i, b_i] to each of [c_i, d_i].

This means that for every i, we inserted O(\log^2 M) edges in our graph. The total edges in our graph becomes O(M + M\log^2M) , and it is not difficult to see that the time taken was O(M\log^2M) as well. Further, as 0-1 BFS takes O(V + E) time, this part also takes O(M\log^2M) time. Hence, our final time complexity is O(M\log^2M).

**Further reducing the time complexity**

We can further reduce the time complexity to O(M\log M) very simply. For each valid i, instead of drawing an edge from each subsegment of [a_i, b_i] to each of [c_i, d_i], we can define an extra vertex v_i and draw an edge from each subsegment of [a_i, b_i] to v_i, followed by an edge from v_i to each subsegment of [c_i, d_i]. As before, we draw these edges of weight 1. Note that we only used O(\log M) edges here instead of O(\log M^2) previously.

With this modification, we can easily show that any edge from p to q in the original graph now corresponds to a path from segment [p, p] to [q, q] of distance 2 in our new graph. Indeed, the only change in the previous proof is that the distance of [a'_i, b'_i] to [c'_i, d'_i] is now 2, but otherwise the same path exists. Thus, we can run 0-1 BFS as before from [x, x] to [y, y] in this graph, but divide by 2 to get the final answer. Since the graph now consists of only O(M\log M) edges, our final time complexity is O(M\log M) as well.

# SOLUTIONS:

## Setter's Solution

```
#include "bits/stdc++.h"
#define endl '\n'
using namespace std;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define rz(v, n) v.resize((n) + 1);
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define vvi vector <vi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const int inf = 1e9;
const int N = 2e5 + 1;
int t, n, m, x, y, xver, yver;
vector <vector<pair <int, bool>>> adj;
void build (int v, int start, int end)
{
if (start == end)
{
adj[v/2].pb({v, 0});
adj[v].pb({4*n + v/2, 0});
if (start == x) xver = v;
if (start == y) yver = v;
}
else
{
adj[v/2].pb({v, 0});
adj[4*n + v].pb({4*n + v/2, 0});
int mid = (start + end)/2;
build(2*v, start, mid);
build(2*v + 1, mid + 1, end);
}
}
void segsearch (int v, int start, int end, int l, int r, int icnt, bool state)
{
int mid = (start + end)/2;
if (start >= l && end <= r)
{
if (state) adj[6*n + icnt].pb({v, 1});
else if (start == end) adj[v].pb({6*n + icnt, 1});
else adj[4*n + v].pb({6*n + icnt, 1});
}
else if (end < l || start > r) return;
else
{
segsearch(2*v, start, mid, l, r, icnt, state);
segsearch(2*v + 1, mid + 1, end, l, r, icnt, state);
}
}
int bfs()
{
vi d(6*n + m + 1, inf);
deque <int> q;
d[xver] = 0;
q.push_front(xver);
while (!q.empty())
{
int v = q.front();
q.pop_front();
for (pi e: adj[v])
{
int u = e.fi, w = e.se;
if (d[v] + w < d[u])
{
d[u] = d[v] + w;
if (w) q.push_back(u);
else q.push_front(u);
}
}
}
if (d[yver] < inf) return d[yver]/2;
else return -1;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--)
{
cin >> n >> m >> x >> y;
vi vec;
set <int> s = {x, y};
FOR (i, 1, m)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
vec.pb(a), vec.pb(b), vec.pb(c), vec.pb(d);
s.insert(a), s.insert(b), s.insert(c), s.insert(d);
}
map <int, int> mp;
int cnt = 0;
for (int i: s) mp[i] = ++cnt;
FOR (i, 0, sz(vec) - 1) vec[i] = mp[vec[i]];
x = mp[x], y = mp[y];
n = sz(s);
adj.clear();
adj.resize(6*n + m + 1);
build(1, 1, n);
int i = 0, icnt = 1;
while (i < sz(vec))
{
segsearch(1, 1, n, vec[i], vec[i + 1], icnt, 0);
segsearch(1, 1, n, vec[i + 2], vec[i + 3], icnt, 1);
i += 4, icnt++;
}
cout << bfs() << endl;
}
}
```

## Tester's Solution

```
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g = getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
cout << x << '\n';
cout << l << ' ' << r << ' ' << (endd == ' ' ? "sp" : "ln") << '\n';
cerr << int(g) << ' ' << char(g) << '\n';
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = readIntLn(1, TEN(5));
int sum_m = 0;
while(t--){
int n, m, x, y;
n = readIntSp(1, TEN(9));
m = readIntSp(1, 2 * TEN(5));
x = readIntSp(1, n);
y = readIntLn(1, n);
sum_m += m;
vector<int> ys;
ys.push_back(n + 1);
ys.push_back(x);
ys.push_back(y);
vector<tuple<int,int,int,int>> edges;
for(int i = 0; i < m; i++){
int a, b, c, d;
a = readIntSp(1, n);
b = readIntSp(a, n);
c = readIntSp(1, n);
d = readIntLn(c, n);
ys.push_back(a);
ys.push_back(b + 1);
ys.push_back(c);
ys.push_back(d + 1);
edges.emplace_back(a, b, c, d);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
auto get_coord = [&](int val){
return lower_bound(ys.begin(), ys.end(), val) - ys.begin();
};
n = ys.size();
x = get_coord(x);
y = get_coord(y);
for(int i = 0; i < m; i++){
auto [a, b, c, d] = edges[i];
a = get_coord(a);
b = get_coord(b + 1) - 1;
c = get_coord(c);
d = get_coord(d + 1) - 1;
edges[i] = make_tuple(a, b, c, d);
}
vector<vector<pair<int,int>>> seg(4 * n);
function<void(int,int,int,vector<tuple<int,int,int,int>>&)> insert_on_seg = [&](int id, int l, int r, vector<tuple<int,int,int,int>> &to){
if(to.empty()) return;
vector<tuple<int,int,int,int>> left, right;
int m = (l + r)>>1;
for(auto [a, b, c, d] : to){
if(l == a && b == r){
seg[id].push_back({c, d});
} else {
if(a > m) right.push_back(make_tuple(a, b, c, d));
else if(b <= m) left.push_back(make_tuple(a, b, c, d));
else {
left.push_back(make_tuple(a, m, c, d));
right.push_back(make_tuple(m + 1, b, c, d));
}
}
}
if(l == r)
return;
insert_on_seg(id<<1, l, m, left);
insert_on_seg(id<<1|1, m + 1, r, right);
};
insert_on_seg(1, 0, n - 1, edges);
vector<pair<int,int>> nxt;
function<void(int,int,int,int)> fill_nxt = [&](int id, int l, int r, int p){
for(auto e : seg[id]) nxt.push_back(e);
seg[id].clear();
if(l == r)
return;
int m = (l + r)>>1;
if(p <= m) fill_nxt(id<<1, l, m, p);
else fill_nxt(id<<1|1, m + 1, r, p);
};
set<int> missing;
for(int i = 0; i < n; i++)
if(i != x)
missing.insert(i);
vector<int> dist(n, -1);
dist[x] = 0;
queue<int> q;
q.push(x);
while(!q.empty()){
int cur = q.front(); q.pop();
nxt.clear();
fill_nxt(1, 0, n - 1, cur);
for(auto [l, r] : nxt){
while(true){
auto p = missing.lower_bound(l);
if(p == missing.end() || *p > r) break;
dist[*p] = dist[cur] + 1;
q.push(*p);
missing.erase(p);
}
}
}
cout << dist[y] << '\n';
}
assert(1 <= sum_m && sum_m <= 2 * TEN(5));
return 0;
}
```