#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int inf = 1e9;
const int MxN = 3e5 + 10;
const int MxL = 32;
int n, m, p, q, g[MxN], vis[MxN][2], dis[MxN][2], cyc[2], up[MxN][MxL];
vector<pii> adj[MxN];
vector<int> radj[MxN];
int neg(int u) {
return u < n ? u + n : u - n;
}
int is_neg(int u, int p) {
if (adj[u][0].second == p) return neg(u);
else return u;
}
void dfs(int u, int st, int i) {
vis[u][i] = true;
for (int v : radj[u]) {
if (v == st && vis[v][i]) cyc[i] = dis[u][i] + 1;
if (!vis[v][i]) {
dis[v][i] = dis[u][i] + 1;
dfs(v, st, i);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n = N, m = M, p = P;
for (int i = 0; i < M; i++) {
int u = R[i][0];
int v = R[i][1];
adj[u].push_back({i, v});
adj[v].push_back({i, u});
}
q = Q;
for (int i = 0; i < Q; i++) {
g[i] = G[i];
}
for (int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
}
for (int i = 0; i < n; i++) {
radj[is_neg(adj[i][0].second, i)].push_back(i);
radj[adj[i].size() < 2 ? is_neg(adj[i][0].second, i) : is_neg(adj[i][1].second, i)].push_back(neg(i));
}
memset(dis, -1, sizeof dis);
dis[p][0] = 0, dis[neg(p)][1] = 0;
dfs(p, p, 0);
dfs(neg(p), neg(p), 1);
for (int i = 0; i < q; i++) {
int ans = 0;
for (int j = 0; j < n; j++) {
int ok = 0;
for (int k = 0; k < 2; k++) {
if (dis[j][k] == -1) continue;
int len = g[i] - dis[j][k];
if (len < 0) continue;
if (cyc[k] == 0 && len == 0) ok = 1;
else if (cyc[k] != 0 && len % cyc[k]) ok = 1;
}
ans += ok;
}
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
21072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
21072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
21072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
