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]);
}
Ahh.... I see, Why you may be getting the Time Limit exceeded verdict. You might not be using "Path Compression" technique, which is why you are facing TLE.
Like, this Find function is implementing.
int Find(int x, int type) { return fa[type][x] == x ? x : fa[type][x] = Find(fa[type][x], type); }
If you are unable to get this recursive function, let me write another find function with Path compression technique.
int Find(int i) { while(i!= id[i]){ i = id[i] ;// This is without Path Compression, But is correct. Might give TLE. }//end of while return i; }
int Find(int i) { while(i!= id[i]){ id[i]=id[id[i]] ;// This is Path Compression Fast & Correct }//end of while return i; }