#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
int n, m, p, r[NMAX][2], q, g[NMAX], e[NMAX][2], a, b, d[NMAX], dd[NMAX], cy2, cy;
vector<int> adj[NMAX];
void add(int a, int b){
if(a % n == e[b][0]) adj[b + n].emplace_back(a);
else adj[b].emplace_back(a);
return;
}
void dfs(int x, int dist){
d[x] = dist;
for(int& nx : adj[x]){
if(d[nx] == -1) dfs(nx, dist + 1);
else if(nx == p) cy = dist + 1;
}
return;
}
/*
void answer(int x){
cout << x << '\n';
return;
}*/
void count_routes(int n_, int m_, int p_, int r_[][2], int q_, int g_[]){
n = n_; m = m_; p = p_; q = q_;
memset(e, -1, sizeof(e));
for(int i = 0; i < m; i++){
a = r_[i][0]; b = r_[i][1];
if(e[a][0] == -1) e[a][0] = b;
else if(e[a][1] == -1) e[a][1] = b;
if(e[b][0] == -1) e[b][0] = a;
else if(e[b][1] == -1) e[b][1] = a;
}
for(int i =0; i < n; i++)
if(e[i][1] == -1) e[i][1] = e[i][0];
for(int i = 0; i < n; i++)
if(e[i][0] != -1){
add(i, e[i][0]);
add(i + n, e[i][1]);
}
memset(d, -1, sizeof(d));
dfs(p, 0);
swap(d, dd); cy2 = cy; cy = 0;
memset(d, -1, sizeof(d));
p += n; dfs(p, 0);
for(int j = 0; j < q; j++){
int ans = 0;
a = g_[j];
for(int i = 0; i < n; i++){
if(d[i] == a || cy && a > d[i] && d[i] != -1 && (a - d[i]) % cy == 0) ans++;
else if(dd[i] == a || cy2 && a > dd[i] && dd[i] != -1 && (a - dd[i]) % cy2 == 0) ans++;
}
answer(ans);
}
return;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> p;
for(int i = 0; i < m; i++) cin >> r[i][0] >> r[i][1];
cin >> q;
for(int i = 0; i < q; i++) cin >> g[i];
count_routes(n, m, p, r, q, g);
return 0;
}*/
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:60:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
60 | if(d[i] == a || cy && a > d[i] && d[i] != -1 && (a - d[i]) % cy == 0) ans++;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:61:67: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
61 | else if(dd[i] == a || cy2 && a > dd[i] && dd[i] != -1 && (a - dd[i]) % cy2 == 0) ans++;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
7 ms |
12116 KB |
Output is correct |
3 |
Correct |
8 ms |
12160 KB |
Output is correct |
4 |
Correct |
6 ms |
12080 KB |
Output is correct |
5 |
Correct |
7 ms |
12020 KB |
Output is correct |
6 |
Correct |
10 ms |
12244 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
12012 KB |
Output is correct |
9 |
Correct |
7 ms |
12188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
7 ms |
12116 KB |
Output is correct |
3 |
Correct |
8 ms |
12160 KB |
Output is correct |
4 |
Correct |
6 ms |
12080 KB |
Output is correct |
5 |
Correct |
7 ms |
12020 KB |
Output is correct |
6 |
Correct |
10 ms |
12244 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
12012 KB |
Output is correct |
9 |
Correct |
7 ms |
12188 KB |
Output is correct |
10 |
Correct |
7 ms |
11988 KB |
Output is correct |
11 |
Correct |
14 ms |
13180 KB |
Output is correct |
12 |
Correct |
21 ms |
13840 KB |
Output is correct |
13 |
Correct |
38 ms |
26052 KB |
Output is correct |
14 |
Correct |
75 ms |
17712 KB |
Output is correct |
15 |
Correct |
117 ms |
19608 KB |
Output is correct |
16 |
Correct |
62 ms |
18124 KB |
Output is correct |
17 |
Correct |
56 ms |
17512 KB |
Output is correct |
18 |
Correct |
23 ms |
14336 KB |
Output is correct |
19 |
Correct |
61 ms |
19324 KB |
Output is correct |
20 |
Correct |
99 ms |
19600 KB |
Output is correct |
21 |
Correct |
71 ms |
17996 KB |
Output is correct |
22 |
Correct |
57 ms |
17536 KB |
Output is correct |
23 |
Correct |
65 ms |
19976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
7 ms |
12116 KB |
Output is correct |
3 |
Correct |
8 ms |
12160 KB |
Output is correct |
4 |
Correct |
6 ms |
12080 KB |
Output is correct |
5 |
Correct |
7 ms |
12020 KB |
Output is correct |
6 |
Correct |
10 ms |
12244 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
12012 KB |
Output is correct |
9 |
Correct |
7 ms |
12188 KB |
Output is correct |
10 |
Correct |
7 ms |
11988 KB |
Output is correct |
11 |
Correct |
14 ms |
13180 KB |
Output is correct |
12 |
Correct |
21 ms |
13840 KB |
Output is correct |
13 |
Correct |
38 ms |
26052 KB |
Output is correct |
14 |
Correct |
75 ms |
17712 KB |
Output is correct |
15 |
Correct |
117 ms |
19608 KB |
Output is correct |
16 |
Correct |
62 ms |
18124 KB |
Output is correct |
17 |
Correct |
56 ms |
17512 KB |
Output is correct |
18 |
Correct |
23 ms |
14336 KB |
Output is correct |
19 |
Correct |
61 ms |
19324 KB |
Output is correct |
20 |
Correct |
99 ms |
19600 KB |
Output is correct |
21 |
Correct |
71 ms |
17996 KB |
Output is correct |
22 |
Correct |
57 ms |
17536 KB |
Output is correct |
23 |
Correct |
65 ms |
19976 KB |
Output is correct |
24 |
Correct |
8 ms |
11988 KB |
Output is correct |
25 |
Correct |
109 ms |
13500 KB |
Output is correct |
26 |
Correct |
166 ms |
14420 KB |
Output is correct |
27 |
Correct |
2200 ms |
27060 KB |
Output is correct |
28 |
Correct |
1067 ms |
19496 KB |
Output is correct |
29 |
Correct |
2606 ms |
19640 KB |
Output is correct |
30 |
Correct |
1396 ms |
18332 KB |
Output is correct |
31 |
Correct |
1468 ms |
17700 KB |
Output is correct |
32 |
Correct |
161 ms |
14464 KB |
Output is correct |
33 |
Correct |
1053 ms |
19412 KB |
Output is correct |
34 |
Correct |
2513 ms |
19708 KB |
Output is correct |
35 |
Correct |
1502 ms |
18228 KB |
Output is correct |
36 |
Correct |
1879 ms |
17612 KB |
Output is correct |
37 |
Correct |
868 ms |
20176 KB |
Output is correct |
38 |
Correct |
2542 ms |
31532 KB |
Output is correct |