#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar()
#define pc(x) putchar(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=char(n%10+48);n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif
#define f first
#define s second
using namespace std;
using pii = pair<int, int>;
const int MM = 150005;
int n, m, p, k;
vector<pii> in[MM];
pii nx[MM][2];
int dis[MM][2], f[MM], s[MM], len, id, cnt[MM], cnta[MM], cntb[MM];
bool vis[MM][2];
//0 = go to best next one
//1 = go to second best one
#ifndef ONLINE_JUDGE
void answer(int X){
print(X);
}
#endif
void go(int cur, bool f, int d){
pr("go", cur, f, d);
vis[cur][f] = 1;
int u, w;
tie(u, w) = nx[cur][f];
if(u == p){
len = d+1;
id = f;
return;
}
if(!vis[u][w])
go(u, w, d+1);
}
int dfs(int cur, bool f){
if(~dis[cur][f])
return dis[cur][f];
dis[cur][f] = 1e9;
return dis[cur][f] = dfs(nx[cur][f].first, nx[cur][f].second)+1;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n = N, m = M, p = P, k = Q;
for(int i = 0; i < m; i++){
in[R[i][0]].emplace_back(i, R[i][1]);
in[R[i][1]].emplace_back(i, R[i][0]);
}
for(int i = 0; i < n; i++){
sort(all(in[i]));
assert(size(in[i]));
if(size(in[i]) == 1)
in[i].emplace_back(in[i][0]);
else
in[i].resize(2);
}
for(int i = 0,u,w; i < n; i++){
tie(w, u) = in[i][0];
nx[i][0] = {u, (w == in[u][0].first)};
tie(w, u) = in[i][1];
nx[i][1] = {u, (w == in[u][0].first)};
pr("nx", i, nx[i][0].f, nx[i][0].s, nx[i][1].f, nx[i][1].s);
}
//find "final" cycle distances
memset(vis, 0, sizeof vis);
len = 1e9, id = -1;
go(p, 0, 0);
int lena = len, ida = id;
pr("a", lena, ida);
memset(vis, 0, sizeof vis);
len = 1e9, id = -1;
go(p, 1, 0);
int lenb = len, idb = id;
pr("b", lenb, idb);
// either no cycle, 0/1 itself cycle, lead into other cycle, or large cycle with both...
int moda, offa, modb, offb;
if(ida == -1){
moda = 1e9;
offa = 1e9;
}
else if(ida == 0){
moda = lena;
offa = 0;
}
else{
moda = lenb;
offa = lena;
}
if(idb == -1){
modb = 1e9;
offb = 1e9;
}
else if(idb == 1){
modb = lenb;
offb = 0;
}
else{
modb = lena;
offb = lenb;
}
if(ida == 1 and idb == 0){
//large cycle with both
// abort();
}
pr("vals", moda, offa, modb, offb, ida, idb);
memset(dis, -1, sizeof dis);
dis[p][0] = 0;
dis[p][1] = 1e8; //to tell apart
// for(int i = 0; i < n; i++){
// int l = dfs(i, 0);
// pr("l", i, l);
// if(l >= 1e9) continue;
// if(l >= 1e8){
// //2nd cycle
// l -= 1e8;
// if(modb != 1e9)
// cntb[(l+offb)%modb]++;
// if((l+offb)%modb != l)
// cnt[l]++;
// }
// else{
// //1st cycle
// if(moda != 1e9)
// cnta[(l+offa)%moda]++;
// if((l+offa)%moda != l)
// cnt[l]++;
// }
// }
int mod2 = (moda+modb);
for(int i = 0; i < Q; i++){
int v = G[i], ans = 0;
for(int j = 0; j < n; j++){
int l = dfs(j, 0);
pr("d", j, l);
if(l >= 1e9) continue;
//large cycle with both
if(ida == 1 and idb == 0){
if(l >= 1e8){
l -= 1e8;
if(l <= v){
l %= mod2;
v %= mod2;
if(l == v or (l+offb)%mod2 == v)
ans++;
}
}
else{
if(l <= v){
l %= mod2;
v %= mod2;
if(l == v or (l+offa)%mod2 == v)
ans++;
}
}
continue;
}
if(l >= 1e8){
l -= 1e8;
//second cycle
if(l == v or (l+offb <= v and (l+offb)%modb == v%modb))
ans++;
}
else{
if(l == v or (l+offa <= v and (l+offa)%moda == v%moda))
ans++;
}
}
// if(moda != 1e9)
// ans += cnta[v%moda];
// if(modb != 1e9)
// ans += cntb[v%modb];
// ans += cnt[v];
answer(ans);
}
}
#ifndef ONLINE_JUDGE
int main(){
int N, M, P;
scan(N, M, P);
int R[M][2];
for(int i = 0; i < M; i++){
scan(R[i][0], R[i][1]);
// print(R[i][0], R[i][1], i);
}
int Q;
scan(Q);
int G[Q];
for(int i = 0; i < Q; i++)
scan(G[i]);
count_routes(N, M, P, R, Q, G);
if(0){
int G[] = {3};
int R[][2] = {{1, 2}, {0, 1}, {0, 3}, {3, 4}, {4, 5}, {1, 5}};
count_routes(6, 6, 0, R, 1, G);
}
if(0){
int G[] = {3, 1};
int R[][2] = {{1, 0}, {1, 2}, {3, 2}, {1, 3}, {4, 2}};
count_routes(5, 5, 2, R, 2, G);
}
}
#endif
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:202:3: error: 'answer' was not declared in this scope
202 | answer(ans);
| ^~~~~~
