#include <iostream> #include <queue> #include "garden.h" #include "gardenlib.h" using namespace std; const int Sz = 3<<17, inf = 2e9; vector<int> nei[Sz], rev[Sz]; int cyc[Sz], seen[Sz], Dfs[Sz], cur, Mn[2][Sz], lst[Sz], bst[Sz], sbst[Sz]; void dfs(int u){ seen[u] = 1; if (Dfs[u]) cyc[u] = cur - lst[u]; lst[u] = cur++; Dfs[u]++; for (int i : nei[u]){ if (Dfs[i] == 2 or (Dfs[i] == 0 and seen[i] == 1)) continue; dfs(i); } Dfs[u]--; } void bfs(int s, int id){ for (int i=0;i<Sz;i++) Mn[id][i] = inf; Mn[id][s] = 0; queue<int> Q; Q.push(s); while (Q.size() > 0){ s = Q.front(); Q.pop(); for (int i : rev[s]){ if (Mn[id][i] > Mn[id][s] + 1) Mn[id][i] = Mn[id][s] + 1, Q.push(i); } } } void count_routes(int n, int m, int p, int R[][2], int q, int g[]){ for (int i=0;i<n;i++) bst[i] = Sz; for (int i=m-1;i>=0;i--){ int a = R[i][0], b = R[i][1]; sbst[a] = bst[a], bst[a] = i; sbst[b] = bst[b], bst[b] = i; } for (int i=0;i<n;i++){ int K = 0; if (sbst[i] == Sz) sbst[i] = bst[i]; for (int e : {bst[i], sbst[i]}){ if (e == Sz) continue; int j = R[e][0] + R[e][1] - i; if (bst[j] == e) j += n; nei[i+K].push_back(j); rev[j].push_back(i+K); K = n; } } for (int i=0;i<n + n;i++){ if (seen[i] == 0) dfs(i); } bfs(p, 0); bfs(p + n, 1); for (int j=0;j<q;j++){ int ans = 0, d = g[j]; for (int i=0;i<n;i++){ bool t = 0; if (Mn[0][i] == d or Mn[1][i] == d) ans++; else if (Mn[0][i] <= d and cyc[p] != 0 and (d - Mn[0][i]) % cyc[p] == 0) ans++; else if (Mn[1][i] <= d and cyc[p+n] != 0 and (d - Mn[1][i]) % cyc[p + n] == 0) ans++; } answer(ans); } }