#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define long long long
using namespace std;
const int V = (int) 1.5E5;
int n, m, x;
vector<pair<int, int>> e[V];
int t[V];
int p[V * 2];
int d[V * 2];
bitset<V * 2> f;
vector<int> a[V * 2];
// int length[2];
int length[V * 2];
void generate() {
queue<int> q;
for (int i = 0; i < n * 2; i++) {
if (d[i] == 0) {
q.push(i);
}
}
while (q.empty() == 0) {
int u = q.front(), v = p[u];
q.pop();
f[u] = 1;
d[v] = d[v] - 1;
if (d[v] == 0) {
q.push(v);
}
}
for (int i = 0; i < n * 2; i++) {
if (f[i] == 0) {
vector<int> a;
for (int u = i; f[u] == 0; u = p[u]) {
a.push_back(u);
f[u] = 1;
}
for (auto u : a) {
length[u] = (int) a.size();
}
}
}
}
bitset<V * 2> state;
int dist1[V * 2];
int dist2[V * 2];
void DFS1(int u) {
state[u] = 1;
for (auto v : a[u]) {
if (state[v] == 0) {
dist1[v] = dist1[u] + 1;
DFS(v);
}
}
}
void DFS2(int u) {
state[u] = 1;
for (auto v : a[u]) {
if (state[v] == 0) {
dist2[v] = dist2[u] + 1;
DFS(v);
}
}
}
int count1(int u, int k) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (length[u] == 0 && dist1[i] == k) {
sum = sum + 1;
}
if (length[u] > 0 && k - dist1[i] >= 0 && (k - dist1[i]) % length[u] == 0) {
sum = sum + 1;
}
}
return sum;
}
int count2(int u, int k) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (length[u] == 0 && dist2[i] == k) {
sum = sum + 1;
}
if (length[u] > 0 && k - dist2[i] >= 0 && (k - dist2[i]) % length[u] == 0) {
sum = sum + 1;
}
}
return sum;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n = N;
m = M;
x = P;
fill(t, t + n, m);
for (int i = 0; i < m; i++) {
int u, v;
u = R[i][0];
v = R[i][1];
e[u].push_back({v, i});
e[v].push_back({u, i});
t[u] = min(t[u], i);
t[v] = min(t[v], i);
}
for (int u = 0; u < n; u++) {
int v, i;
tie(v, i) = e[u][0];
if (i != t[v]) {
p[u] = v;
d[v] = d[v] + 1;
a[v].push_back(u);
} else {
p[u] = v + n;
d[v + n] = d[v + n] + 1;
a[v + n].push_back(u);
}
if ((int) e[u].size() > 1) {
tie(v, i) = e[u][1];
}
if (i != t[v]) {
p[u + n] = v;
d[v] = d[v] + 1;
a[v].push_back(u + n);
} else {
p[u + n] = v + n;
d[v + n] = d[v + n] + 1;
a[v + n].push_back(u + n);
}
}
generate();
state.reset();
fill(dist1, dist1 + n * 2, (int) 1E9);
dist1[x] = 0;
DFS1(x);
state.reset();
fill(dist2, dist2 + n * 2, (int) 1E9);
dist2[x + n] = 0;
DFS2(x + n);
int q = Q;
for (int i = 0; i < q; i++) {
int k = G[i];
answer(count1(x, k) + count2(x + n, k));
// cout << count(x, k) + count(x + n, k) << " ";
}
}
Compilation message
garden.cpp: In function 'void DFS1(int)':
garden.cpp:64:13: error: 'DFS' was not declared in this scope; did you mean 'DFS1'?
64 | DFS(v);
| ^~~
| DFS1
garden.cpp: In function 'void DFS2(int)':
garden.cpp:74:13: error: 'DFS' was not declared in this scope; did you mean 'DFS2'?
74 | DFS(v);
| ^~~
| DFS2
