#include <bits/stdc++.h>
using namespace std;
int gl;
int ps[(int)15e4+2][2];
int vis[(int)15e4+2][2];
int ds[(int)15e4+2][2];
int gd[(int)15e4+2][2];
int a1 = 0; int a2 = 0;
int g1 = 0; int g2 = 0;
int dfs1(int p, int last, int len){
int nx;
if (last == ps[p][0]) nx = 1;
else nx = 0;
if (p==gl) return len * (2*nx-1);
if (vis[p][nx]) return (int)1e7;
vis[p][nx] = 1;
return dfs1(ps[p][nx], p, len+1);
}
void answer(int x);
// void answer(int x){
// cout<<x<<'\n';
// }
void dfs2(int p, int last){
int nx; if (last == ps[p][0]) nx = 1; else nx = 0;
if (p == gl){
gd[p][nx] = nx;
ds[p][nx] = 0;
return;
}
if (ds[p][nx]) return;
if (vis[p][nx]){
ds[p][nx] = (int)-1e5;
return;
}
vis[p][nx] = 1;
int nxt = ps[p][nx];
int d; if (p == ps[nxt][0]) d = 1; else d = 0;
dfs2(nxt, p);
gd[p][nx] = gd[nxt][d];
ds[p][nx] = ds[nxt][d]+1;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
gl = P;
for (int i=0; i<N; i++) ps[i][0]=-1, ps[i][1]=-1;
for (int i=0; i<M; i++){
int a = R[i][0]; int b= R[i][1];
if (ps[a][0]==-1) ps[a][0] = b; else if (ps[a][1]==-1) ps[a][1] = b;
if (ps[b][0]==-1) ps[b][0] = a; else if (ps[b][1]==-1) ps[b][1] = a;
}
for (int i=0; i<N; i++) if (ps[i][1]==-1) ps[i][1] = ps[i][0];
for (int i=0; i<N; i++) vis[i][0] = 0, vis[i][1] = 0;
int r1 = dfs1(ps[P][0], P, 1);
for (int i=0; i<N; i++) vis[i][0] = 0, vis[i][1] = 0;
int r2 = dfs1(ps[P][1], P, 1);
if (r1!=1e7) {
if (r1>0) g1 = 1;
a1 = abs(r1);
}
if (r2!=1e7){
if (r2>0) g2 = 1;
a2 = abs(r2);
}
for (int i=0; i<N; i++) vis[i][0] = 0, vis[i][1] = 0;
for (int i=0; i<N; i++) ds[i][0] = 0, ds[i][1] = 0;
for (int i=0; i<N; i++) {
if (i==P) continue;
if (!ds[i][0]) dfs2(i, -1);
}
for (int q = 0; q<Q; q++){
int k = G[q];
int ans = 0;
for (int i=0; i<N; i++){
if (ds[i][0] < 0) continue;
if (k<ds[i][0]) continue;
int t= k - ds[i][0];
if (gd[i][0]==0 || (i==P && g1==0)){
if (a1 == 0) continue;
if (g1 == 0 && t%a1 == 0) ans++;
if (g1 == 1 && a2 == 0 && (t==0 || t==a1)) ans++;
if (g1 == 1 && g2 == 0 && (t%(a1+a2)==0 || t%(a1+a2)==a1)) ans++;
if (t && t<a1) continue;
if (g1 == 1 && g2 == 1 && (t==0 || (t-a1)%a2 == 0)) ans++;
} else {
swap(a1,a2); swap(g1,g2);
if (a1 == 0) {swap(a1,a2); swap(g1,g2);continue;}
if (g1 == 0 && t%a1 == 0) ans++;
if (g1 == 1 && a2 == 0 && (t==0 || t==a1)) ans++;
if (g1 == 1 && g2 == 0 && (t%(a1+a2)==0 || t%(a1+a2)==a1)) ans++;
if (t && t<a1) {swap(a1,a2); swap(g1,g2);continue;}
if (g1 == 1 && g2 == 1 && (t==0 || (t-a1)%a2 == 0)) ans++;
swap(a1,a2); swap(g1,g2);
}
}
answer(ans);
}
}
// int main(){
// // int n = 5; int m = 5;
// // int p=2;int q = 2; int g[] = {3,1};
// // int r[][2]= {
// // {1,0},
// // {1,2},
// // {3,2},
// // {1,3},
// // {4,2}
// // };
// // count_routes(n,m,p,r,q,g);
// // int n = 6; int m = 6;
// // int p=0;int q = 1; int g[] = {3};
// // int r[][2]= {
// // {1,2},
// // {0,1},
// // {0,3},
// // {3,4},
// // {4,5},
// // {1,5}
// // };
// // count_routes(n,m,p,r,q,g);
// int n = 5; int m = 4;
// int p=0;int q = 10; int g[] = {100,101,102,103,104,105,106,107,108,109};
// int r[][2]= {
// {0,1},
// {1,2},
// {2,3},
// {3,4}
// };
// count_routes(n,m,p,r,q,g);
// // cout<<'\n';
// // for (int i=0; i<n; i++){
// // cout<<i<<' '<<jump(i, 4)<<'\n';
// // }
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
