#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define eb emplace_back
using ii = pair<int, int>;
int cur_rt, ans[600050], cnt[600050], _cnt2[600050], dr[600050], link[300005], rt[600050], sz[600050], to[600050], *cnt2 = _cnt2 + 300005;
bool on_cyc[600050], out[600050];
vector<int> in_nodes, adj[600050];
vector<ii> _adj[600050], qu[600050];
int find(int x) {
if (x == link[x]) return x;
return link[x] = find(link[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[b] > sz[a]) swap(a, b);
sz[a] += sz[b];
link[b] = a;
}
void dfs(int n, int e = -1, int d = 0) {
rt[n] = cur_rt;
dr[n] = d;
for (auto u : adj[n]) if (u != e && !on_cyc[u]) dfs(u, n, d + 1);
}
void dfs2(int n, int e = -1, int d = 0) {
if (out[n]) cnt[d]++;
if (!on_cyc[n])
for (auto [j, idx] : qu[n])
ans[idx] += cnt[d - j];
for (auto u : adj[n]) if (u != e && !on_cyc[u]) dfs2(u, n, d + 1);
if (out[n]) cnt[d]--;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
for (int i = 0; i < M; i++) {
_adj[R[i][0]].eb(i, i << 1);
_adj[R[i][1]].eb(i, i << 1 | 1);
}
iota(link, link + 2 * M, 0);
fill(sz, sz + 2 * M, 1);
for (int i = 0; i < N; i++) sort(_adj[i].begin(), _adj[i].end());
for (int i = 0; i < M; i++) {
if (_adj[R[i][1]].size() == 1) to[i << 1] = (i << 1) ^ 1;
else to[i << 1] = ((_adj[R[i][1]][0].second >> 1) == i ? _adj[R[i][1]][1].second : _adj[R[i][1]][0].second);
if (_adj[R[i][0]].size() == 1) to[i << 1 | 1] = (i << 1 | 1) ^ 1;
else to[i << 1 | 1] = ((_adj[R[i][0]][0].second >> 1) == i ? _adj[R[i][0]][1].second : _adj[R[i][0]][0].second);
}
for (int i = 0; i < N; i++)
if (!_adj[i].empty()) in_nodes.pb(_adj[i][0].second);
for (int i = 0; i < M; i++) {
if (R[i][0] == P) out[i << 1 | 1] = 1;
if (R[i][1] == P) out[i << 1] = 1;
}
for (int i = 0; i < 2 * M; i++) {
unite(i, to[i]);
adj[to[i]].pb(i);
}
for (int i = 0; i < 2 * M; i++) {
if (i == find(i)) {
int tort = i, hare = i;
do {
tort = to[tort];
hare = to[to[hare]];
} while (tort != hare);
do {
on_cyc[tort] = 1;
tort = to[tort];
} while (tort != hare);
do {
cur_rt = tort;
dfs(tort);
tort = to[tort];
} while (tort != hare);
}
}
for (int i = 0, ans, curr, OG; i < Q; i++) {
G[i]--;
for (int j : in_nodes) {
if (G[i] >= dr[j]) qu[rt[j]].eb(G[i] - dr[j], i);
else qu[j].eb(G[i], i);
}
}
for (int i = 0; i < 2 * M; i++)
if (on_cyc[i]) dfs2(i);
for (int i = 0; i < 2 * M; i++) {
if (i == find(i)) {
vector<int> upd;
int tort = i, hare = i;
do {
tort = to[tort];
hare = to[to[hare]];
} while (tort != hare);
int cyc = 0, off = 0, steps = 0;
do {
cyc++;
upd.pb(steps);
if (out[tort]) cnt2[steps]++;
tort = to[tort];
steps++;
} while (tort != hare);
do {
for (auto [j, idx] : qu[tort])
ans[idx] += cnt2[j % cyc - off];
if (out[tort]) {
upd.pb(-off);
upd.pb(cyc - off);
cnt2[-off]--;
cnt2[cyc - off]++;
}
off--;
tort = to[tort];
} while (tort != hare);
for (int j : upd) cnt2[j] = 0;
}
}
for (int i = 0; i < Q; i++) answer(ans[i]);
}
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:89:18: warning: unused variable 'ans' [-Wunused-variable]
89 | for (int i = 0, ans, curr, OG; i < Q; i++) {
| ^~~
garden.cpp:89:23: warning: unused variable 'curr' [-Wunused-variable]
89 | for (int i = 0, ans, curr, OG; i < Q; i++) {
| ^~~~
garden.cpp:89:29: warning: unused variable 'OG' [-Wunused-variable]
89 | for (int i = 0, ans, curr, OG; i < Q; i++) {
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
42828 KB |
Output is correct |
2 |
Correct |
23 ms |
42748 KB |
Output is correct |
3 |
Correct |
27 ms |
42764 KB |
Output is correct |
4 |
Correct |
23 ms |
42652 KB |
Output is correct |
5 |
Correct |
26 ms |
42572 KB |
Output is correct |
6 |
Correct |
28 ms |
43048 KB |
Output is correct |
7 |
Correct |
22 ms |
42644 KB |
Output is correct |
8 |
Correct |
22 ms |
42828 KB |
Output is correct |
9 |
Correct |
25 ms |
43476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
42828 KB |
Output is correct |
2 |
Correct |
23 ms |
42748 KB |
Output is correct |
3 |
Correct |
27 ms |
42764 KB |
Output is correct |
4 |
Correct |
23 ms |
42652 KB |
Output is correct |
5 |
Correct |
26 ms |
42572 KB |
Output is correct |
6 |
Correct |
28 ms |
43048 KB |
Output is correct |
7 |
Correct |
22 ms |
42644 KB |
Output is correct |
8 |
Correct |
22 ms |
42828 KB |
Output is correct |
9 |
Correct |
25 ms |
43476 KB |
Output is correct |
10 |
Correct |
21 ms |
42648 KB |
Output is correct |
11 |
Correct |
44 ms |
46416 KB |
Output is correct |
12 |
Correct |
73 ms |
49804 KB |
Output is correct |
13 |
Correct |
66 ms |
59324 KB |
Output is correct |
14 |
Correct |
186 ms |
63324 KB |
Output is correct |
15 |
Correct |
227 ms |
63988 KB |
Output is correct |
16 |
Correct |
192 ms |
60300 KB |
Output is correct |
17 |
Correct |
178 ms |
59512 KB |
Output is correct |
18 |
Correct |
67 ms |
49660 KB |
Output is correct |
19 |
Correct |
231 ms |
63160 KB |
Output is correct |
20 |
Correct |
193 ms |
63860 KB |
Output is correct |
21 |
Correct |
198 ms |
60096 KB |
Output is correct |
22 |
Correct |
206 ms |
59244 KB |
Output is correct |
23 |
Correct |
178 ms |
65248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
42828 KB |
Output is correct |
2 |
Correct |
23 ms |
42748 KB |
Output is correct |
3 |
Correct |
27 ms |
42764 KB |
Output is correct |
4 |
Correct |
23 ms |
42652 KB |
Output is correct |
5 |
Correct |
26 ms |
42572 KB |
Output is correct |
6 |
Correct |
28 ms |
43048 KB |
Output is correct |
7 |
Correct |
22 ms |
42644 KB |
Output is correct |
8 |
Correct |
22 ms |
42828 KB |
Output is correct |
9 |
Correct |
25 ms |
43476 KB |
Output is correct |
10 |
Correct |
21 ms |
42648 KB |
Output is correct |
11 |
Correct |
44 ms |
46416 KB |
Output is correct |
12 |
Correct |
73 ms |
49804 KB |
Output is correct |
13 |
Correct |
66 ms |
59324 KB |
Output is correct |
14 |
Correct |
186 ms |
63324 KB |
Output is correct |
15 |
Correct |
227 ms |
63988 KB |
Output is correct |
16 |
Correct |
192 ms |
60300 KB |
Output is correct |
17 |
Correct |
178 ms |
59512 KB |
Output is correct |
18 |
Correct |
67 ms |
49660 KB |
Output is correct |
19 |
Correct |
231 ms |
63160 KB |
Output is correct |
20 |
Correct |
193 ms |
63860 KB |
Output is correct |
21 |
Correct |
198 ms |
60096 KB |
Output is correct |
22 |
Correct |
206 ms |
59244 KB |
Output is correct |
23 |
Correct |
178 ms |
65248 KB |
Output is correct |
24 |
Correct |
27 ms |
44672 KB |
Output is correct |
25 |
Runtime error |
523 ms |
262148 KB |
Execution killed with signal 9 |
26 |
Halted |
0 ms |
0 KB |
- |