#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[300005], cnt[300005], _cnt2[600005], dr[300005], link[300005], rt[300005], sz[300005], to[300005], *cnt2 = _cnt2 + 300000;
bool on_cyc[300005], out[300005];
vector<int> in_nodes, adj[300005];
vector<ii> _adj[300005], qu[300005];
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)) {
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++;
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]) {
cnt2[-off]--;
cnt2[cyc - 1 - off]++;
}
off--;
tort = to[tort];
} while (tort != hare);
}
}
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 |
Incorrect |
15 ms |
21708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
21708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
21708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
