PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Shreshth Walia
Tester: Smit Mandavia
Editorialist: Jenish Monpara
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
PROBLEM:
There is one N x M grid. The rows of the grid are numbered from 1 to N, top to bottom. The columns of the grid numbered from 1 to M, left to right. (x1,y1) is connected to (x2,y2) if there exists a continuous path in the grid connecting them. There are two types queries:
Type 1 query : A hollow sub-rectangle is chosen in the grid and the cells lying on the border of rectangle will be blocked. The top-leftmost cell of sub-rectangle will be (x1,y1) and down-rightmost cell will be (x2,y2).
All the sub-rectangles in first type of event are non overlapping. But they can be nested. Consider sub-rectangles as hollow rectangular frames
Type 2 query : Given two cells (x1,y1) and (x2,y2, we have to check if they are connected or not. (x1,y1) and (x2,y2) don’t lie on border of some sub-rectangle.
QUICK EXPLANATION:
Find all the connected components after the last type 1 query. Now process all queries in reverse order. If you encounter a type 1 query, link the components of the cells bordering the border of sub-rectangle and also add rectangle’s border cells in the same resulting component. If you encounter a type 2 query, check if both the cells belong to same connected component or not.
EXPLANATION:
After reading quick explanation, you might be wondering why are we processing queries in a reverse fashion. Here is why. Initially whole grid is one large connected component and as we go on processing type 1 queries, we go on breaking it down into more components. Breaking down components and keeping their track is the problem!
If you want to break a component into two, you will have to colour(or mark) whole component into two colours. This is very inefficient as in this case for one type 1 query you will have to recolour the whole grid.
Think why?
So that you can tell for any type 2 query if any two cells belong to same component. Since one of the cell can belong to one of the newly formed component, you will have to link/de-link this new component with other remaining cells of the whole grid.
What now?
We have efficient way to link two connected components (pre-requisite : DSU). Rather than de-linking components, we can link two de-linked components and answer the queries if we process them in reverse order.
We don’t need to mark components initially! We just need to define their borders. And we can start processing in reverse fashion. It will become more clear after you have read till last. Here is how…
First process all type 1 queries and mark the border cells only.
Now, check all the cells of the grid, and if any cell if unvisited and not marked as border, start a BFS from the cell( consider cell as node and has edges to its four adjacent neighbours which shares common border). While doing BFS only process cells which are not on the border and are not visited. Colour all the cells processed during i^{th} BFS with colour i.
After processing all the type 1 queries this way, the cells coloured with i^{th} colour will belong to i^{th} connected component.
And in this way we have all the components separated by rectangles at last. Since any cell is visited during a BFS or marked as border cell only once, this would take N.M time at max because the borders in type 1 query are given to be non overlapping.
Now let us start processing queries in reverse order. If you encounter a type 1 query, demolish the rectangle border corresponding to that query. Here demolishing implies linking the components of the cells bordering the border of sub-rectangle and also add rectangle’s border cells in the same resulting component. If you encounter a type 2 query, check if both the cells belong to same connected component or not and store the answer.
Proof of correctness
Consider some i^{th} query in input as type 1.
All the type 2 queries which appear after this i^{th} query are affected by the border created in i^{th} query. While processing any of these type 2 queries in reverse fashion, we have not yet demolished the border created during i^{th} query. And hence the effects of i^{th} rectangle remains, same way it would have if we processed in normal fashion.
All the type 2 queries which appear before the i^{th} query are not affected by that rectangle as it did not existed while processing them. During reverse processing, we are demolishing the rectangle corresponding to i^{th} query before these type 2 queries and we link back the components it sliced. So the effect of i^{th} rectangle is undone before processing these queries. In normal fashion also this i^{th} would have no effect on these type 2 queries because it appears after them.
Hence proved, processing in reverse fashion this way creates no difference.
Finally print all the answers stored for type 2 queries while processing in reverse fashion, but this time in normal order xD
SOLUTIONS:
Setter's Solution
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define hackcyborg shresth_walia
#define all(a) a.begin(), a.end()
#define ll long long
#define ld long double
#define pb push_back
#define mod 1000000007
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<int,null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
ll bp(ll a,ll b)
{
ll res=1;
while(b>0)
{
if(b&1)
res=(a*res)%mod;
a=(a*a)%mod;
b/=2;
}
return res;
}
struct UF {
vi e;
UF(int n) : e(n, -1) {}
bool sameSet(int a, int b) { return find(a) == find(b); }
int size(int x) { return -e[find(x)]; }
int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
bool join(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (e[a] > e[b]) swap(a, b);
e[a] += e[b]; e[b] = a;
return true;
}
};
struct que
{
int t,l1,r1,l2,r2;
};
ll n,m,q;
vector<vi> a;
UF Tree(5000000);
void fun(ll x,ll y)
{
if(a[x][y]==0)
{
if(x-1>0 && a[x-1][y]==0)
Tree.join(((x-1)*m)+y,(x-2)*m+y);
if(x+1<=n && a[x+1][y]==0)
Tree.join(((x-1)*m)+y,((x)*m)+y);
if(y-1>0 && a[x][y-1]==0)
Tree.join(((x-1)*m)+y,((x-1)*m)+y-1);
if(y+1<=m && a[x][y+1]==0)
Tree.join(((x-1)*m)+y,((x-1)*m)+y+1);
}
}
main()
{
IO
cin>>n>>m>>q;
a.resize(n+1, vector<int>(m+1,0));
vector<que> ad;
while(q--)
{ que u;
cin>>u.t>>u.l1>>u.r1>>u.l2>>u.r2;
if(u.t==1)
{for(int x=u.l1;x<=u.l2;x++)
{
a[x][u.r1]=1;
a[x][u.r2]=1;
}
for(int x=u.r1;x<=u.r2;x++)
{
a[u.l1][x]=1;
a[u.l2][x]=1;
}
}
ad.pb(u);
}
for(int x=1;x<=n;x++)
{
for(int y=1;y<=m;y++)
{
fun(x,y);
}
}
reverse(all(ad));
vector<string> as;
for(auto it : ad)
{
if(it.t==2)
{
if(Tree.sameSet(((it.l1-1)*m)+it.r1,((it.l2-1)*m)+it.r2))
as.pb("YES");
else
as.pb("NO");
}
else
{
for(int x=it.l1;x<=it.l2;x++)
{
a[x][it.r1]=0;
fun(x,it.r1);
a[x][it.r2]=0;
fun(x,it.r2);
}
for(int x=it.r1;x<=it.r2;x++)
{
a[it.l1][x]=0;
fun(it.l1,x);
a[it.l2][x]=0;
fun(it.l2,x);
}
}
}
reverse(all(as));
for(auto it : as)
cout<<it<<"\n";
}