#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 150000 + 10;
const int INF = 1e9;
int n, m, p, q;
int dp[MAXN][2];
int cnt[MAXN][2];
std::vector <std::pair <int,int>> g[MAXN];
bool vis[MAXN][2];
void dfs(int node, bool next, int edges, bool firstEdge)
{
if (next == false)
{
cnt[edges][firstEdge]++;
}
int l = 0, r = g[node].size();
if (next || g[node].size() == 1)
{
r = 1;
} else
{
l = 1;
}
for (int i = l ; i < r ; ++i)
{
auto [u, t] = g[node][i];
if (u == p)
{
continue;
}
if (t == g[u][0].second)
{
dfs(u, 0, edges + 1, firstEdge);
continue;
}
if (t == g[u][1].second)
{
dfs(u, 1, edges + 1, firstEdge);
continue;
}
}
}
std::pair <int,int> dfsCycle(int node, bool fromMAX, int time)
{
if (time != 0 && node == p)
{
return {time, fromMAX};
}
if (vis[node][fromMAX])
{
return {-1, -1};
}
vis[node][fromMAX] = true;
if (!fromMAX || g[node].size() == 1)
{
return dfsCycle(g[node][0].first, (g[node][0].second == g[g[node][0].first][0].second), time + 1);
} else
{
return dfsCycle(g[node][1].first, (g[node][1].second == g[g[node][1].first][0].second), time + 1);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
m = M;
p = P + 1;
q = Q;
for (int i = 0 ; i < m ; ++i)
{
g[R[i][0] + 1].push_back({R[i][1] + 1, i + 1});
g[R[i][1] + 1].push_back({R[i][0] + 1, i + 1});
}
for (int i = 1 ; i <= n ; ++i)
{
std::sort(g[i].begin(), g[i].end(), [&](auto a, auto b)
{
return a.second < b.second;
});
}
cnt[0][0]++;
vis[p][0] = vis[p][1] = true;
for (const auto &[u, t] : g[p])
{
if (t == g[u][0].second)
{
dfs(u, 0, 1, (t == g[p][0].second));
continue;
}
if (t == g[u][1].second)
{
dfs(u, 1, 1, (t == g[p][0].second));
continue;
}
}
std::pair <int,int> cycle[2];
memset(vis, false, sizeof(vis));
cycle[0] = dfsCycle(p, 0, 0);
memset(vis, false, sizeof(vis));
cycle[1] = dfsCycle(p, 1, 0);
for (int i = 0 ; i < q ; ++i)
{
int k = G[i];
int ans = 0;
for (int fromMAX = 0 ; fromMAX < 2 ; ++fromMAX)
{
for (int j = 0 ; j <= std::min(n, k) ; ++j)
{
if (j == k)
{
ans += cnt[j][fromMAX];
continue;
}
if (cycle[fromMAX].first == -1)
{
continue;
}
if (j + cycle[fromMAX].first == k)
{
ans += cnt[j][fromMAX];
continue;
}
if (cycle[fromMAX].second == fromMAX)
{
if ((k - j) % cycle[fromMAX].first == 0)
{
ans += cnt[j][fromMAX];
}
continue;
}
if (cycle[fromMAX ^ 1].first == -1)
{
continue;
}
if (cycle[fromMAX ^ 1].second == (fromMAX ^ 1))
{
if ((k - j - cycle[fromMAX].first) % cycle[fromMAX ^ 1].first == 0)
{
ans += cnt[j][fromMAX];
}
continue;
}
int rem = (k - j) % (cycle[fromMAX].first + cycle[fromMAX ^ 1].first)
if (rem == 0 || rem == cycle[fromMAX].first)
{
ans += cnt[j][fromMAX];
continue;
}
}
}
answer(ans);
}
}
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:177:17: error: expected ',' or ';' before 'if'
177 | if (rem == 0 || rem == cycle[fromMAX].first)
| ^~
garden.cpp:176:21: warning: unused variable 'rem' [-Wunused-variable]
176 | int rem = (k - j) % (cycle[fromMAX].first + cycle[fromMAX ^ 1].first)
| ^~~
