[HELP] Dynamic Connectivity Problem

Revision en1, by Abhi1857, 2020-04-13 18:16:24

Problem:D: Stamp Rally

I implemented DSU but its exceeding time limit, I read the editorial and understood nothing, I tried to read other AC of this problem. It seems people have implemented some recursive function, I am not able to comprehend. Any resources or explanations will be of great help.

I am posting a sample AC of this problem and I don't understand how Divide/Conquer this problem

#include<cstdio>
const int MAXN = 100000;
struct edge{
	int u, v;	
}edges[MAXN + 5];
int fa[20][MAXN + 5], siz[20][MAXN + 5];
int Find(int x, int type) {
	return fa[type][x] == x ? x : fa[type][x] = Find(fa[type][x], type);
}
void Union(int x, int y, int type) {
	int fx = Find(x, type), fy = Find(y, type);
	if( fx != fy ) {
		siz[type][fy] += siz[type][fx];
		fa[type][fx] = fy;
	}
}
struct query{
	int x, y, z;
	int ind;
}qry[MAXN + 5], tmp[MAXN + 5];
int ans[MAXN + 5];
bool Check(query q, int type) {
	if( Find(q.x, type) == Find(q.y, type) )
		return siz[type][Find(q.x, type)] >= q.z;
	else return siz[type][Find(q.x, type)] + siz[type][Find(q.y, type)] >= q.z;
}
void Divide_Conquer(int L, int R, int le, int ri, int dep) {
	if( le == ri ) {
		for(int i=L;i<=R;i++)
			ans[qry[i].ind] = le;
		Union(edges[le].u, edges[le].v, dep);//It's necessary!!!
		return ;
	}
	int mid = (le + ri) >> 1;
	for(int i=le;i<=mid;i++)
		Union(edges[i].u, edges[i].v, dep);
	int p = L-1, q = R+1;
	for(int i=L;i<=R;i++)
		if( Check(qry[i], dep) ) tmp[++p] = qry[i];
		else tmp[--q] = qry[i];
	for(int i=L;i<=R;i++)
		qry[i] = tmp[i];
	for(int i=mid+1;i<=ri;i++)
		Union(edges[i].u, edges[i].v, dep);
	Divide_Conquer(L, p, le, mid, dep+1);
	Divide_Conquer(q, R, mid+1, ri, dep+1);
}
int main() {
	int N, M, Q;
	scanf("%d%d", &N, &M);
	for(int i=1;i<=N;i++)
		for(int j=0;j<20;j++)
			fa[j][i] = i, siz[j][i] = 1;
	for(int i=1;i<=M;i++)
		scanf("%d%d", &edges[i].u, &edges[i].v);
	scanf("%d", &Q);
	for(int i=1;i<=Q;i++) {
		scanf("%d%d%d", &qry[i].x, &qry[i].y, &qry[i].z);
		qry[i].ind = i;
	}
	Divide_Conquer(1, Q, 1, M, 0);
	for(int i=1;i<=Q;i++)
		printf("%d\n", ans[i]);
}
Tags #help, #dsu

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Abhi1857 2020-04-13 18:16:24 2247 Initial revision (published)