#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int Nmax = 3e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
#include "garden.h"
#include "gardenlib.h"
#include "grader.cpp"
vector <int> adj[Nmax];
vector <int> vt[Nmax];
vector <int> s;
pair <int, int> ed[Nmax];
pair <int, int> mn[Nmax];
int anc[Nmax][20];
int ptr[Nmax];
int h[Nmax];
int n,m,p,q,cnt;
bool flag[Nmax];
bool vis[Nmax];
bool ins[Nmax];
bool cyc[Nmax];
bool ok[Nmax];
void dfs(int i) {
if (ins[i]) {
cnt++;
int j;
do {
j = s.back();
s.pop_back();
cyc[j] = true;
ins[j] = false;
vt[cnt].push_back(j);
} while (j != i);
reverse(ALL(vt[cnt]));
return;
}
if (vis[i])
return;
vis[i] = true;
ins[i] = true;
s.push_back(i);
dfs(ptr[i]);
if (ins[i]) {
ins[i] = false;
s.pop_back();
}
}
void build() {
m <<= 1;
for (int i = 0; i < n; i++)
mn[i] = mp(oo, oo);
for (int i = 0; i < m; i++) {
int u = ed[i].fi;
int v = ed[i].se;
mini(mn[u].se, i);
if (mn[u].se < mn[u].fi)
swap(mn[u].fi, mn[u].se);
}
for (int i = 0; i < m; i++) {
int u = ed[i].fi;
int v = ed[i].se;
if (mn[v].fi == (i ^ 1)) {
if (mn[v].se == oo)
ptr[i] = (i ^ 1);
else
ptr[i] = mn[v].se;
} else {
ptr[i] = mn[v].fi;
}
}
for (int i = 0; i < m; i++) if (!vis[i]) {
s.clear();
dfs(i);
}
for (int i = 0; i < m; i++)
adj[ptr[i]].push_back(i);
for (int i = 0; i < n; i++)
flag[mn[i].fi] = true;
}
void solve(int u, vector <int> &vt, int cur, int k) {
if (cur < 0)
cur = (int) vt.size() - 1;
s.push_back(u);
int sz = s.size();
if (flag[u]) {
if (sz > k) {
int v = s[sz - k - 1];
if (ed[v].se == p)
ok[u] = true;
} else {
int v = vt[cur];
if (ed[v].se == p)
ok[u] = true;
}
}
for (int v : adj[u])
if (!cyc[v])
solve(v, vt, cur - 1, k);
s.pop_back();
}
int solve(int k) {
for (int i = 0; i < m; i++)
ok[i] = false;
k--;
for (int i = 1; i <= cnt; i++)
for (int j = 0, cur = k % (int) vt[i].size(); j < (int) vt[i].size(); j++) {
solve(vt[i][j], vt[i], cur, k);
cur++;
if (cur == (int) vt[i].size())
cur = 0;
}
int res = 0;
for (int i = 0; i < n; i++)
res += ok[mn[i].fi];
return res;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for (int i = 0; i < M; i++)
for (int j = 0; j < 2; j++)
ed[i << 1 | j] = mp(R[i][j], R[i][j ^ 1]);
n = N;
m = M;
p = P;
q = Q;
build();
for (int i = 0; i < q; i++)
answer(solve(G[i]));
}
Compilation message
garden.cpp: In function 'void build()':
garden.cpp:77:13: warning: unused variable 'v' [-Wunused-variable]
77 | int v = ed[i].se;
| ^
garden.cpp:84:13: warning: unused variable 'u' [-Wunused-variable]
84 | int u = ed[i].fi;
| ^
/usr/bin/ld: /tmp/ccOIYCQQ.o: in function `read_input()':
grader.cpp:(.text+0x0): multiple definition of `read_input()'; /tmp/ccDkHdHQ.o:garden.cpp:(.text+0xa0): first defined here
/usr/bin/ld: /tmp/ccOIYCQQ.o: in function `answer(int)':
grader.cpp:(.text+0x130): multiple definition of `answer(int)'; /tmp/ccDkHdHQ.o:garden.cpp:(.text+0x1d0): first defined here
/usr/bin/ld: /tmp/ccOIYCQQ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccDkHdHQ.o:garden.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
