#include "gardenlib.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
int n;
vector<int> edge[155555];
vector<int> gph[333333],rev[333333];
int cyc;
int dfn[333333];
int ans1[333333],ans2[333333];
bool is_gone[333333];
void dfs1(int v,int p,int dist){
if(dfn[v]){
cyc=dist-dfn[v];
return;
}
dfn[v]=dist;
for(int u:gph[v]){
if(u==p) continue;
dfs1(u,v,dist+1);
}
}
void dfs2(int v,int p,int dist){
//printf("%d %d!\n",v,dist);
is_gone[v]=1;
if(v%2==0){
for(int i=dist;i<=(n<<1);i+=cyc) ans1[i]++;
ans2[dist%cyc]++;
}
for(int u:rev[v]){
if(u==p || is_gone[u]) continue;
dfs2(u,v,dist+1);
}
is_gone[v]=0;
}
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++){
edge[R[i][0]].push_back(R[i][1]);
edge[R[i][1]].push_back(R[i][0]);
}
for(int i=0;i<N;i++){
if(edge[i].size()>2) edge[i].resize(2);
if(edge[i].size()==1) edge[i].push_back(edge[i][0]);
if(edge[edge[i][0]][0]==i){
gph[i<<1].push_back(edge[i][0]<<1|1);
rev[edge[i][0]<<1|1].push_back(i<<1);
}
else{
gph[i<<1].push_back(edge[i][0]<<1);
rev[edge[i][0]<<1].push_back(i<<1);
}
if(edge[edge[i][1]][0]==i){
gph[i<<1|1].push_back(edge[i][1]<<1|1);
rev[edge[i][1]<<1|1].push_back(i<<1|1);
}
else{
gph[i<<1|1].push_back(edge[i][1]<<1);
rev[edge[i][1]<<1].push_back(i<<1|1);
}
}
//for(int i=0;i<(N<<1);i++){
// printf("#%d : ",i);
// for(int j:rev[i]) printf("%d ",j);
// printf("\n");
//}
dfs1(0,0,1);
//printf("cyc%d\n",cyc);
dfs2(P<<1,P<<1,0);
dfs2(P<<1|1,P<<1|1,0);
//for(int i=0;i<(N<<1);i++) printf("%d ",ans1[i]); printf("\n");
//for(int i=0;i<cyc;i++) printf("%d ",ans2[i]); printf("\n");
//printf("%d\n",cyc);
//for(int i=0;i<(N<<1);i++) printf("%d ",ans1[i]); printf("\n");
//for(int i=0;i<cyc;i++) printf("%d ",ans2[i]); printf("\n");
for(int i=0;i<Q;i++){
if(G[i]>(N<<1)) answer(ans2[G[i]%cyc]);
else answer(ans1[G[i]]);
}
return;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
19896 KB |
Output is correct |
2 |
Correct |
20 ms |
19832 KB |
Output is correct |
3 |
Correct |
21 ms |
19896 KB |
Output is correct |
4 |
Correct |
20 ms |
19608 KB |
Output is correct |
5 |
Correct |
20 ms |
19676 KB |
Output is correct |
6 |
Correct |
21 ms |
19984 KB |
Output is correct |
7 |
Correct |
19 ms |
19660 KB |
Output is correct |
8 |
Correct |
21 ms |
19744 KB |
Output is correct |
9 |
Correct |
23 ms |
19984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
19896 KB |
Output is correct |
2 |
Correct |
20 ms |
19832 KB |
Output is correct |
3 |
Correct |
21 ms |
19896 KB |
Output is correct |
4 |
Correct |
20 ms |
19608 KB |
Output is correct |
5 |
Correct |
20 ms |
19676 KB |
Output is correct |
6 |
Correct |
21 ms |
19984 KB |
Output is correct |
7 |
Correct |
19 ms |
19660 KB |
Output is correct |
8 |
Correct |
21 ms |
19744 KB |
Output is correct |
9 |
Correct |
23 ms |
19984 KB |
Output is correct |
10 |
Incorrect |
19 ms |
19664 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
19896 KB |
Output is correct |
2 |
Correct |
20 ms |
19832 KB |
Output is correct |
3 |
Correct |
21 ms |
19896 KB |
Output is correct |
4 |
Correct |
20 ms |
19608 KB |
Output is correct |
5 |
Correct |
20 ms |
19676 KB |
Output is correct |
6 |
Correct |
21 ms |
19984 KB |
Output is correct |
7 |
Correct |
19 ms |
19660 KB |
Output is correct |
8 |
Correct |
21 ms |
19744 KB |
Output is correct |
9 |
Correct |
23 ms |
19984 KB |
Output is correct |
10 |
Incorrect |
19 ms |
19664 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |