#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
vector<int> togo(2*n+1,-1);
for (int i = 0; i < m; i++) {
auto [a,b] = r[i];
if (!~togo[2*a]) togo[2*a] = 2*b+(!~togo[2*b]);
else if (!~togo[2*a+1]) togo[2*a+1] = 2*b+(!~togo[2*b]);
if (!~togo[2*b]) togo[2*b] = 2*a+(togo[2*a]/2==b);
else if (!~togo[2*b+1]) togo[2*b+1] = 2*a+(togo[2*a]/2==b);
}
n *= 2;
vector<vector<int>> adj(n+1);
for (int i = 0; i < n; i++) {
if (!~togo[i]) togo[i] = togo[i-1];
adj[togo[i]].push_back(i);
}
vector<int> cmp(n+1), dist(n+1), to(n+1,-1), ind(n+1); vector<vector<int>> cyc(n+1); int cc = 0;
for (int i = 0; i < n; i++) if (!cmp[i]) {
int cur = i; ++cc;
while (!cmp[cur]) {
cmp[cur] = cc, cur = togo[cur];
}
int o = cur; queue<int> qq;
do {
ind[cur] = (int)cyc[cc].size(); cyc[cc].push_back(cur); to[cur] = cur; qq.push(cur);
} while ((cur = togo[cur]) != o);
while (!qq.empty()) {
int cur = qq.front(); qq.pop();
for (int j : adj[cur]) if (!~to[j]) {
to[j] = to[cur]; cmp[j] = cc;
dist[j] = dist[cur] + 1;
qq.push(j);
}
}
}
array<vector<int>,2> temp;
temp[0].resize(n); temp[1].resize(n);
for (int i = 2*p; i <= 2*p+1; i++) if (dist[i]) {
queue<int> qq; qq.push(i); int par = i % 2;
fill(temp[par].begin(),temp[par].end(),1e9);
temp[par][i] = 0;
while (!qq.empty()) {
int cur = qq.front(); qq.pop();
for (int j : adj[cur]) if (temp[par][cur] + 1 < temp[par][j]) {
temp[par][j] = temp[par][cur] + 1;
qq.push(j);
}
}
}
for (int i = 0; i < q; i++) {
int ret = 0, k = g[i];
for (int i = 0; i < n; i += 2) ret += temp[0][i] == k || temp[1][i] == k || (dist[i] <= k && cyc[cmp[i]][(ind[to[i]] + k - dist[i]) % ((int)cyc[cmp[i]].size())]/2 == p);
answer(ret);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
1 ms |
512 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
1 ms |
512 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
13 ms |
5248 KB |
Output is correct |
| 12 |
Correct |
31 ms |
8064 KB |
Output is correct |
| 13 |
Correct |
47 ms |
19948 KB |
Output is correct |
| 14 |
Correct |
133 ms |
26360 KB |
Output is correct |
| 15 |
Correct |
141 ms |
26856 KB |
Output is correct |
| 16 |
Correct |
92 ms |
18808 KB |
Output is correct |
| 17 |
Correct |
87 ms |
15992 KB |
Output is correct |
| 18 |
Correct |
33 ms |
7936 KB |
Output is correct |
| 19 |
Correct |
138 ms |
26360 KB |
Output is correct |
| 20 |
Correct |
140 ms |
26868 KB |
Output is correct |
| 21 |
Correct |
103 ms |
18680 KB |
Output is correct |
| 22 |
Correct |
90 ms |
15992 KB |
Output is correct |
| 23 |
Correct |
141 ms |
29304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
1 ms |
512 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
13 ms |
5248 KB |
Output is correct |
| 12 |
Correct |
31 ms |
8064 KB |
Output is correct |
| 13 |
Correct |
47 ms |
19948 KB |
Output is correct |
| 14 |
Correct |
133 ms |
26360 KB |
Output is correct |
| 15 |
Correct |
141 ms |
26856 KB |
Output is correct |
| 16 |
Correct |
92 ms |
18808 KB |
Output is correct |
| 17 |
Correct |
87 ms |
15992 KB |
Output is correct |
| 18 |
Correct |
33 ms |
7936 KB |
Output is correct |
| 19 |
Correct |
138 ms |
26360 KB |
Output is correct |
| 20 |
Correct |
140 ms |
26868 KB |
Output is correct |
| 21 |
Correct |
103 ms |
18680 KB |
Output is correct |
| 22 |
Correct |
90 ms |
15992 KB |
Output is correct |
| 23 |
Correct |
141 ms |
29304 KB |
Output is correct |
| 24 |
Correct |
2 ms |
384 KB |
Output is correct |
| 25 |
Correct |
378 ms |
5368 KB |
Output is correct |
| 26 |
Correct |
669 ms |
8184 KB |
Output is correct |
| 27 |
Correct |
1312 ms |
20076 KB |
Output is correct |
| 28 |
Correct |
2866 ms |
26492 KB |
Output is correct |
| 29 |
Correct |
2886 ms |
28532 KB |
Output is correct |
| 30 |
Correct |
1799 ms |
20344 KB |
Output is correct |
| 31 |
Correct |
1602 ms |
17528 KB |
Output is correct |
| 32 |
Correct |
615 ms |
8440 KB |
Output is correct |
| 33 |
Correct |
2890 ms |
28152 KB |
Output is correct |
| 34 |
Correct |
2851 ms |
28552 KB |
Output is correct |
| 35 |
Correct |
1762 ms |
20088 KB |
Output is correct |
| 36 |
Correct |
1611 ms |
17528 KB |
Output is correct |
| 37 |
Correct |
3092 ms |
30968 KB |
Output is correct |
| 38 |
Correct |
2313 ms |
36548 KB |
Output is correct |
