#include "garden.h" #include "gardenlib.h" #include "bits/stdc++.h" using namespace std; const int MAXN = 150000; const int MAXM = 150000; int Rf[MAXN]; int Rs[MAXN]; int succreal[MAXN][30]; int succfake[MAXN][30]; bool _second_path_real[MAXN][30]; bool _second_path_fake[MAXN][30]; bool fake; int cur,curval,a,x,y,i,j; int succ(int x, int k) { fake = false; while (k) { curval = (int) floor(log2(k)); cur = pow(2,curval); k-=cur; if (!fake) { if (_second_path_real[x][curval]) fake = true; x = succreal[x][curval]; } else { if (!_second_path_fake[x][curval]) fake = false; x = succfake[x][curval]; } } return x; } void count_routes(int n, int m, int p, int R[][2], int q, int G[]) { fill(Rf,Rf+n,-1); fill(Rs,Rs+n,-1); for (int i = 0; i<m; i++) { x = R[i][0], y = R[i][1]; if (Rf[x] == -1) Rf[x] = y; else if (Rs[x] == -1) Rs[x] = y; if (Rf[y] == -1) Rf[y] = x; else if (Rs[y] == -1) Rs[y] = x; } for (i = 0; i<n; i++) if (Rs[i] == -1) Rs[i] = Rf[i]; for (j = 0; j<n; j++) { succreal[j][0] = Rf[j]; if (Rf[Rf[j]] == j) _second_path_real[j][0] = true; succfake[j][0] = Rs[j]; if (Rf[Rs[j]] == j) _second_path_fake[j][0] = true; } for (i = 1; i<30; i++) { for (j = 0; j<n; j++) { if (_second_path_real[j][i-1]) { succreal[j][i] = succfake[succreal[j][i-1]][i-1]; _second_path_real[j][i] = _second_path_fake[succreal[j][i-1]][i-1]; } else { succreal[j][i] = succreal[succreal[j][i-1]][i-1]; _second_path_real[j][i] = _second_path_real[succreal[j][i-1]][i-1]; } if (_second_path_fake[j][i-1]) { succfake[j][i] = succfake[succfake[j][i-1]][i-1]; _second_path_fake[j][i] = _second_path_fake[succfake[j][i-1]][i-1]; } else { succfake[j][i] = succreal[succfake[j][i-1]][i-1]; _second_path_fake[j][i] = _second_path_real[succfake[j][i-1]][i-1]; } } } for (i = 0; i<q; i++) { a = 0; for (j = 0; j<n; j++) if (succ(j,G[i]) == p) a++; answer(a); } }