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]);
}