#include "garden.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 3e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;
vector<int> g[N],g2[N];
int n,d[2][N],to[N],fr[2],frd[2][2];
bool vis[N];
bool go(int t,int rem){
if(!rem)return 1;
if(rem < 0 || fr[t])return 0;
if(fr[t] == t)return (rem%frd[t][t])==0;
rem %= frd[t][!t] + frd[!t][t];
return go(!t,rem - frd[t][!t]);
}
void bfs(int s,int t){
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(s);
d[t][s] = 0;
while(q.size()){
int u = q.front();
q.pop();
if(vis[u])continue;
vis[u] = 1;
for(int i=0;i<g[u].size();i++){
int v = g[u][i];
if(d[t][v] != -1)continue;
d[t][v] = d[t][u] + 1;
q.push(v);
}
}
}
void cycle(int s,int t){
memset(vis,0,sizeof(vis));
int cur = to[s];
int d = 1;
while(!vis[cur]){
if(cur == s){
fr[t] = 0;
frd[t][0] = d;
break;
}
if(cur == (s+n)%n){
fr[t] = 1;
frd[t][1] = d;
break;
}
d++;
cur = to[cur];
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n = N;
for(int i=0;i<M;i++){
int u = R[i][0];
int v = R[i][1];
if(g[u].size() < 2)g[u].push_back(v);
if(g[v].size() < 2)g[v].push_back(u);
}
for(int i=n;i<2*n;i++){
g[i] = g[i-n];
if(g[i].size() == 2)swap(g[i][0],g[i][1]);
}
for(int i=0;i<2*n;i++){
int v = g[u][0];
if(g[v][0] == i%n)v += n;
to[i] = v;
g2[v].push_back(i);
}
memset(d,-1,sizeof(d));
memset(frd,-1,sizeof(frd));
fr[0] = fr[1] = -1;
bfs(P,0);
bfs(P+n,1);
cycle(P,0);
cycle(P+n,1);
for(int i=0;i<Q;i++){
int dist = G[i];
int ans = 0;
for(int j=0;j<n;j++){
bool o=0,t=0;
if(d[0][j] != -1){
int rem = dist - d[0][j];
o = go(0,rem);
}
if(d[1][j] != -1){
int rem = dist - d[1][j];
t = go(1,rem);
}
ans += o|t;
}
answer(ans);
}
}
Compilation message
garden.cpp: In function 'void bfs(int, int)':
garden.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++){
~^~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:76:19: error: 'u' was not declared in this scope
int v = g[u][0];
^
garden.cpp:103:9: error: 'answer' was not declared in this scope
answer(ans);
^~~~~~
garden.cpp:103:9: note: suggested alternative: 'ans'
answer(ans);
^~~~~~
ans
