#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,cur1,cur2; void succ() { fake = false; while (cur2) { curval = (int) floor(log2(cur2)); cur = pow(2,curval); cur2-=cur; if (!fake) { if (_second_path_real[cur1][curval]) fake = true; cur1 = succreal[cur1][curval]; } else { if (!_second_path_fake[cur1][curval]) fake = false; cur1 = succfake[cur1][curval]; } } } 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, cur2 = G[i]; for (cur1 = 0; cur1<n; cur1++) { succ(); if (cur1 == p) a++; } answer(a); } }