#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
#define B 150000
using namespace std;
vector<int> v(2*B);
vector<vector<int>> adj(B),T(B*2);
vector<bool> vis(2*B);
int sz=0;
int* G;
bool findcyclic(int x,int st){
if(vis[x]&&x==st)return 1;
else if(vis[x])return 0;
vis[x]=1;
sz++;
bool ret=findcyclic(v[x],st);
vis[x]=0;
return ret;
}
int bfs(int x,int ii,int sz){
queue<pair<int,int>> q;
vector<bool> vv(B*2);
q.push({x,0});
int ans=0;
while(!q.empty()){
int node=q.front().first,we=q.front().second;
q.pop();
if(we>G[ii]||vv[node])continue;
vv[node]=1;
if(sz==0){
if(we==G[ii]&&node<B)ans++;
}else{
if(0==(G[ii]-we)%sz&&node<B)ans++;
}
for(auto i:T[node]){
if(!vv[node]&&we<=G[ii])q.push({i,we+1});
}
}
return ans;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
::G=G;
for(int i=0;i<M;i++){
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
for(int i=0;i<N;i++){
if(i==adj[adj[i][0]][0])v[i]=adj[i][0]+B;
else v[i]=adj[i][0];
if(adj[i].size()>=2){
if(adj[adj[i][1]][0]==i)v[B+i]=adj[i][1]+B;
else v[B+i]=adj[i][1];
}
else v[B+i]=v[i];
}
int sz1=0,sz2=0;
if(findcyclic(P,P)){
sz1=sz;
}
sz=0;
if(findcyclic(P+B,P+B)){
sz2=sz;
}
sz=0;
for(int i=0;i<N;i++){
T[v[i]].push_back(i);
T[v[i+B]].push_back(i+B);
}
for(int i=0;i<Q;i++)answer(bfs(P,i,sz1)+bfs(P+B,i,sz2));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
12112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
