#include "garden.h"
#include <vector>
#include <assert.h>
#include <iostream>
#include <algorithm>
#define vi vector<int>
const int INF = 1e9;
using namespace std;
vi sadj[150001], adj[300001];
int dst[2][300001], cyc[2];
vi ans[2][300001];
void DFS(int u, int id)
{
// cout << u << " " << id << " " << dst[id][u] << "\n";
for (auto v : adj[u])
{
if (dst[id][v] == INF)
{
dst[id][v] = dst[id][u] + 1;
DFS(v, id);
}
else
{
assert(cyc[id] == -1 && dst[id][v] == 0);
cyc[id] = dst[id][u] + 1;
}
}
}
/*
It is possible to represent the problem as a digraph with 2N nodes
such that each node has at most one outgoing edge.
We can use this property to determine which cycle lengths are valid.
*/
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for (int i = 0; i < M; i++)
{
sadj[R[i][0]].push_back(R[i][1]);
sadj[R[i][1]].push_back(R[i][0]);
}
cyc[0] = cyc[1] = -1;
for (int u = 0; u < N; u++)
{
for (int j = 0; j < min(2, (int)sadj[u].size()); j++)
{
int v = sadj[u][j];
//cout << "Add edge " << 2 * u + j << " -> " << 2 * v + (sadj[v].size() > 1 && u == sadj[v][0]) << "\n";
adj[2 * v + (sadj[v].size() > 1 && u == sadj[v][0])].push_back(2 * u + j);
}
}
for (int i = 0; i < 2 * N; i++) {dst[0][i] = dst[1][i] = INF;}
for (int i = 0; i < 2; i++)
{
dst[i][2 * P + i] = 0;
DFS(2 * P + i, i);
if (cyc[i] == -1)
{
for (int j = 0; j < 2 * N; j += 2)
{
if (dst[i][j] < INF) ans[i][0].push_back(dst[i][j]);
}
sort(ans[i][0].begin(), ans[i][0].end());
}
else
{
for (int j = 0; j < 2 * N; j += 2)
{
if (dst[i][j] < INF) ans[i][dst[i][j] % cyc[i]].push_back(dst[i][j]);
}
for (int j = 0; j < cyc[i]; j++)
{
sort(ans[i][j].begin(), ans[i][j].end());
}
}
}
for (int i = 0; i < Q; i++)
{
int ret = 0;
for (int j = 0; j < 2; j++)
{
if (cyc[j] == -1)
{
ret += upper_bound(ans[j][0].begin(), ans[j][0].end(), G[i]) - lower_bound(ans[j][0].begin(), ans[j][0].end(), G[i]);
}
else
{
int v = G[i] % cyc[j];
ret += upper_bound(ans[j][v].begin(), ans[j][v].end(), G[i]) - ans[j][v].begin();
}
}
answer(ret);
}
}
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:97:3: error: 'answer' was not declared in this scope
97 | answer(ret);
| ^~~~~~
