#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int n, m, q, P;
vector<vector<int>> R;
vector<int> succ;
vector<int> cnt;
vector<int> mx, smx;
vector<int> state;
vector<int> cycle_nodes;
vector<vector<pair<int, int>>> cycle_p;
vector<vector<int>> path_p;
int node(int e){ return e < m ? R[e][0]:R[e-m][1]; };
void dfs(int nd){
if(state[nd] > 0){
if(state[nd] == 1) cycle_nodes.pb(nd);
return;
}
state[nd] = 1;
dfs(succ[nd]);
state[nd] = 2;
}
void dfs2(int nd){
if(state[nd]) return;
state[nd] = 1;
dfs2(succ[nd]);
if(node(nd) == P) path_p[nd].pb(0);
for(int x: path_p[succ[nd]]) path_p[nd].pb(x+1);
for(auto [a, b]: cycle_p[succ[nd]]) cycle_p[nd].pb({a+1, b});
}
void count_routes(int _n, int _m, int _P, int _R[][2], int _q, int G[]){
swap(n, _n), swap(m, _m), swap(P, _P), swap(q, _q);
for(int i = 0; i < m; i++) R.pb({_R[i][0], _R[i][1]});
succ.resize(2*m);
cnt.assign(n+1, 0);
mx.assign(n, -1), smx.assign(n, -1);
for(int i = 0; i < m; i++){
if(i < mx[R[i][0]]%m || mx[R[i][0]] == -1) smx[R[i][0]] = mx[R[i][0]], mx[R[i][0]] = i+m;
else if(i < smx[R[i][0]]%m || smx[R[i][0]] == -1) smx[R[i][0]] = i+m;
if(i < mx[R[i][1]]%m || mx[R[i][1]] == -1) smx[R[i][1]] = mx[R[i][1]], mx[R[i][1]] = i;
else if(i < smx[R[i][1]]%m || smx[R[i][1]] == -1) smx[R[i][1]] = i;
}
for(int i = 0; i < n; i++) if(smx[i] == -1) smx[i] = mx[i];
for(int i = 0; i < m; i++) succ[i] = (mx[R[i][0]]%m != i ? mx[R[i][0]]:smx[R[i][0]]);
for(int i = m; i < 2*m; i++) succ[i] = (mx[R[i-m][1]]%m != i-m ? mx[R[i-m][1]]:smx[R[i-m][1]]);
state.assign(2*m, 0);
for(int i = 0; i < n; i++) dfs(mx[i]);
cycle_p.resize(2*m);
path_p.resize(2*m);
state.assign(2*m, 0);
for(int nd: cycle_nodes){
int ln = 1;
if(node(nd) == P) cycle_p[nd].pb({0, -1});
int x = succ[nd];
while(x != nd){
if(node(x) == P) cycle_p[nd].pb({ln, -1});
ln++;
x = succ[x];
}
for(auto &[a, b]: cycle_p[nd]) b = ln;
state[nd] = 1;
}
for(int i = 0; i < n; i++) dfs2(mx[i]);
vector<pair<int, int>> op;
for(int i = 0; i < n; i++){
for(int x: path_p[mx[i]]) cnt[x+1]++;
for(auto [a, b]: cycle_p[mx[i]]) op.pb({a+1, b});
}
for(int i = 0; i < q; i++){
int ans = 0;
if(G[i] <= n) ans+=cnt[G[i]];
for(auto [a, b]: op) if(a <= G[i] && (G[i]-a)%b == 0) ans++;
answer(ans);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
700 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
3 ms |
1748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
700 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
3 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
9 ms |
4756 KB |
Output is correct |
12 |
Correct |
21 ms |
10008 KB |
Output is correct |
13 |
Correct |
48 ms |
30080 KB |
Output is correct |
14 |
Correct |
65 ms |
28404 KB |
Output is correct |
15 |
Correct |
85 ms |
38136 KB |
Output is correct |
16 |
Correct |
69 ms |
32364 KB |
Output is correct |
17 |
Correct |
59 ms |
29448 KB |
Output is correct |
18 |
Correct |
19 ms |
9856 KB |
Output is correct |
19 |
Correct |
60 ms |
28168 KB |
Output is correct |
20 |
Correct |
88 ms |
37868 KB |
Output is correct |
21 |
Correct |
88 ms |
33004 KB |
Output is correct |
22 |
Correct |
84 ms |
30672 KB |
Output is correct |
23 |
Correct |
60 ms |
29172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
700 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
3 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
9 ms |
4756 KB |
Output is correct |
12 |
Correct |
21 ms |
10008 KB |
Output is correct |
13 |
Correct |
48 ms |
30080 KB |
Output is correct |
14 |
Correct |
65 ms |
28404 KB |
Output is correct |
15 |
Correct |
85 ms |
38136 KB |
Output is correct |
16 |
Correct |
69 ms |
32364 KB |
Output is correct |
17 |
Correct |
59 ms |
29448 KB |
Output is correct |
18 |
Correct |
19 ms |
9856 KB |
Output is correct |
19 |
Correct |
60 ms |
28168 KB |
Output is correct |
20 |
Correct |
88 ms |
37868 KB |
Output is correct |
21 |
Correct |
88 ms |
33004 KB |
Output is correct |
22 |
Correct |
84 ms |
30672 KB |
Output is correct |
23 |
Correct |
60 ms |
29172 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
34 ms |
4880 KB |
Output is correct |
26 |
Correct |
29 ms |
10016 KB |
Output is correct |
27 |
Correct |
2160 ms |
30120 KB |
Output is correct |
28 |
Correct |
454 ms |
29944 KB |
Output is correct |
29 |
Correct |
2335 ms |
40172 KB |
Output is correct |
30 |
Correct |
1360 ms |
33948 KB |
Output is correct |
31 |
Correct |
1325 ms |
31052 KB |
Output is correct |
32 |
Correct |
21 ms |
10472 KB |
Output is correct |
33 |
Correct |
457 ms |
30064 KB |
Output is correct |
34 |
Correct |
2341 ms |
39828 KB |
Output is correct |
35 |
Correct |
1491 ms |
33588 KB |
Output is correct |
36 |
Correct |
1355 ms |
32436 KB |
Output is correct |
37 |
Correct |
264 ms |
30828 KB |
Output is correct |
38 |
Correct |
2039 ms |
56500 KB |
Output is correct |