#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
int a,k,n,m,q,p,v1[300005],sz,sz1,sz2,st,ch,res;
bool fx[300005];
vector<pair<int,int> >v[150005];
vector<int>rv[300005];
inline void cch(int x,int dis,int st){
for(vector<int> :: iterator it=rv[x].begin();it!=rv[x].end();it++){
if(*it==st) {sz=dis+1;return;}
cch(*it,dis+1,st);
}
}
inline void dfs(int x,int dis,int st){
if(k<dis) return;
if((x&1)==0 && abs(k-dis)%sz==0)
{
res+=(1^fx[x]);
fx[x]=1;
}
for(vector<int> :: iterator it=rv[x].begin();it!=rv[x].end();it++){
if(*it==st) continue;
dfs(*it,dis+1,st);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int n=N,m=M,p=P;
for(int i=0;i<m;i++){///grafi1
v[R[i][0]].push_back({i,R[i][1]});
v[R[i][1]].push_back({i,R[i][0]});
}
for(int i=0;i<n;i++){
sort(v[i].begin(),v[i].end());
}
for(int i=0;i<n;i++){///grafi2
if(v[i].size()==1)
{
int to=v[i][0].second;
int val=v[i][0].first;
if(v[to][0].first==val)
v1[2*i+1]=2*to+1;
else
v1[2*i+1]=2*to;
if(v[to][0].first==val)
v1[2*i]=2*to+1;
else
v1[2*i]=2*to;
}
else
{
int to=v[i][0].second;
int val=v[i][0].first;
// cout<<i<<" "<<to<<" "<<val<<" "<<v[to][0].first<<endl;
if(v[to][0].first==val)
v1[2*i]=2*to+1;
else
v1[2*i]=2*to;
to=v[i][1].second;
val=v[i][1].first;
// cout<<i<<" "<<to<<" "<<val<<" "<<v[to][0].first<<endl;
if(v[to][0].first==val)
v1[2*i+1]=2*to+1;
else
v1[2*i+1]=2*to;
}
}
for(int i=0;i<2*n;i++){
rv[v1[i]].push_back(i);
}
sz=1000000003;cch(2*p,0,2*p);sz1=sz;
sz=1000000003;cch(2*p+1,0,2*p+1);sz2=sz;
for(int i=0; i<Q; i++)
{
k=G[i];
for(int j=0;j<2*n;j++)
fx[j]=0;
res=0;
sz=sz1;dfs(2*p,0,2*p);
sz=sz2;dfs(2*p+1,0,2*p+1);
answer(res);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
10972 KB |
Output is correct |
2 |
Correct |
12 ms |
11260 KB |
Output is correct |
3 |
Correct |
12 ms |
11000 KB |
Output is correct |
4 |
Correct |
12 ms |
10904 KB |
Output is correct |
5 |
Correct |
12 ms |
11000 KB |
Output is correct |
6 |
Correct |
12 ms |
11128 KB |
Output is correct |
7 |
Correct |
12 ms |
10872 KB |
Output is correct |
8 |
Correct |
12 ms |
11000 KB |
Output is correct |
9 |
Correct |
12 ms |
11196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
10972 KB |
Output is correct |
2 |
Correct |
12 ms |
11260 KB |
Output is correct |
3 |
Correct |
12 ms |
11000 KB |
Output is correct |
4 |
Correct |
12 ms |
10904 KB |
Output is correct |
5 |
Correct |
12 ms |
11000 KB |
Output is correct |
6 |
Correct |
12 ms |
11128 KB |
Output is correct |
7 |
Correct |
12 ms |
10872 KB |
Output is correct |
8 |
Correct |
12 ms |
11000 KB |
Output is correct |
9 |
Correct |
12 ms |
11196 KB |
Output is correct |
10 |
Correct |
13 ms |
10972 KB |
Output is correct |
11 |
Correct |
33 ms |
13052 KB |
Output is correct |
12 |
Correct |
47 ms |
14684 KB |
Output is correct |
13 |
Correct |
68 ms |
25092 KB |
Output is correct |
14 |
Correct |
153 ms |
23100 KB |
Output is correct |
15 |
Correct |
191 ms |
23516 KB |
Output is correct |
16 |
Correct |
151 ms |
20560 KB |
Output is correct |
17 |
Correct |
139 ms |
19704 KB |
Output is correct |
18 |
Correct |
50 ms |
14768 KB |
Output is correct |
19 |
Correct |
166 ms |
23160 KB |
Output is correct |
20 |
Correct |
209 ms |
23372 KB |
Output is correct |
21 |
Correct |
171 ms |
20468 KB |
Output is correct |
22 |
Correct |
155 ms |
19680 KB |
Output is correct |
23 |
Correct |
168 ms |
24176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
10972 KB |
Output is correct |
2 |
Correct |
12 ms |
11260 KB |
Output is correct |
3 |
Correct |
12 ms |
11000 KB |
Output is correct |
4 |
Correct |
12 ms |
10904 KB |
Output is correct |
5 |
Correct |
12 ms |
11000 KB |
Output is correct |
6 |
Correct |
12 ms |
11128 KB |
Output is correct |
7 |
Correct |
12 ms |
10872 KB |
Output is correct |
8 |
Correct |
12 ms |
11000 KB |
Output is correct |
9 |
Correct |
12 ms |
11196 KB |
Output is correct |
10 |
Correct |
13 ms |
10972 KB |
Output is correct |
11 |
Correct |
33 ms |
13052 KB |
Output is correct |
12 |
Correct |
47 ms |
14684 KB |
Output is correct |
13 |
Correct |
68 ms |
25092 KB |
Output is correct |
14 |
Correct |
153 ms |
23100 KB |
Output is correct |
15 |
Correct |
191 ms |
23516 KB |
Output is correct |
16 |
Correct |
151 ms |
20560 KB |
Output is correct |
17 |
Correct |
139 ms |
19704 KB |
Output is correct |
18 |
Correct |
50 ms |
14768 KB |
Output is correct |
19 |
Correct |
166 ms |
23160 KB |
Output is correct |
20 |
Correct |
209 ms |
23372 KB |
Output is correct |
21 |
Correct |
171 ms |
20468 KB |
Output is correct |
22 |
Correct |
155 ms |
19680 KB |
Output is correct |
23 |
Correct |
168 ms |
24176 KB |
Output is correct |
24 |
Correct |
13 ms |
10872 KB |
Output is correct |
25 |
Correct |
157 ms |
13048 KB |
Output is correct |
26 |
Correct |
173 ms |
14780 KB |
Output is correct |
27 |
Execution timed out |
5067 ms |
25140 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |