#include"bits/stdc++.h"
#include "garden.h"
#include "gardenlib.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
//void answer(int ans){cout<<ans<<endl;}
void count_routes(int n,int m,int p,int r[][2],int q,int query[]){
vector<int>to(2*n,-1);
vector<int>cnt(n);
vector<int>deg(n);
rep(i,m){
deg[r[i][0]]++,deg[r[i][1]]++;
}
rep(i,m){
int u=r[i][0],v=r[i][1];
if(to[u]==-1)to[u]=((deg[v]>1&&to[v]==-1)?v+n:v);
else if(to[u+n]==-1)to[u+n]=((deg[v]>1&&to[v]==-1)?v+n:v);
if(to[v]==-1)to[v]=((deg[u]>1&&to[u]==v)?u+n:u);
else if(to[v+n]==-1)to[v+n]=((deg[u]>1&&to[u]==v)?u+n:u);
}
//rep(i,n)if(to[i+n]==-1)to[i+n]=to[i];
vector<int>dist1(2*n,2e9),dist2(2*n,2e9);
vector<vector<int>>rg(2*n);
for(int i=0;i<2*n;++i)if(to[i]!=-1)rg[to[i]].eb(i);
{
queue<int>que;
que.emplace(p);
dist1[p]=0;
while(!que.empty()){
int v=que.front();que.pop();
for(auto u:rg[v])if(dist1[u]>dist1[v]+1){
dist1[u]=dist1[v]+1;
que.emplace(u);
}
}
}
{
queue<int>que;
que.emplace(p+n);
dist2[p+n]=0;
while(!que.empty()){
int v=que.front();que.pop();
for(auto u:rg[v])if(dist2[u]>dist2[v]+1){
dist2[u]=dist2[v]+1;
que.emplace(u);
}
}
}
int cycle1=2e9,cycle2=2e9;
{
int now=p;
rep(i,1,2*n+1){
now=to[now];
if(now==p){
cycle1=i;
break;
}
}
}
{
int now=p+n;
rep(i,1,2*n+1){
now=to[now];
if(now==p+n){
cycle2=i;
break;
}
}
}
rep(i,q){
int k=query[i];
int ans=0;
rep(j,n){
if(k>=dist1[j]&&(k-dist1[j])%cycle1==0)ans++;
else if(k>=dist2[j]&&(k-dist2[j])%cycle2==0)ans++;
}
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
