#include "garden.h"
#include "gardenlib.h"
#include <stdbool.h>
#include <string.h>
#include <assert.h>
int dsu_find(int *par, int a) {
return par[a] < 0 ? a : (par[a] = dsu_find(par, par[a]));
}
void dsu_union(int *par, int a, int b) {
a = dsu_find(par, a);
b = dsu_find(par, b);
assert(a != b); // we should only call dsu_union if they belong to different components
if (-par[b] > -par[a]) {
int tmp = a;
a = b;
b = tmp;
}
par[a] += par[b];
par[b] = a;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
static int most_beautiful[150001][2];
static int graph[300001];
static int dsu[300001];
static int rem[2][300001];
int cyc[2];
cyc[0] = cyc[1] = 1e9 + 1;
memset(dsu, -1, sizeof dsu[0] * (2 * (size_t)N + 1));
assert(dsu[2 * N] == -1);
// 1 indexing, graph[u] == 0, means no edges connected to it
P++;
// save 2 most_beautiful edges
for (int i = 0; i < M; i++) {
for (int j = 0; j < 2; j++) {
int u = R[i][j] + 1;
int v = R[i][j^1] + 1;
if (most_beautiful[u][0] == 0) {
most_beautiful[u][0] = v;
} else if (most_beautiful[u][1] == 0) {
most_beautiful[u][1] = v;
}
}
}
// build functional graph
for (int u = 1; u <= N; u++) {
for (int j = 0; j < 2; j++) {
int v = most_beautiful[u][j];
if (most_beautiful[v][0] != u || most_beautiful[v][1] == 0)
graph[u + j*N] = v;
else
graph[u + j*N] = v + N;
}
}
// set everything in cycle
for (int u = 1; u <= 2 * N; u++) {
if (graph[u] == 0) continue;
if (dsu_find(dsu, u) != dsu_find(dsu, graph[u])) {
dsu_union(dsu, u, graph[u]);
continue;
}
bool seen[2] = {false};
int c = 0;
int v = u;
do {
v = graph[v];
seen[0] = seen[0] || v == P;
seen[1] = seen[1] || v == P + N;
rem[0][v] = rem[1][v] = -1;
c++;
} while (v != u);
for (int i = 0; i < 2; i++) {
if (!seen[i]) continue;
cyc[i] = c;
v = graph[P + i * N];
for (int j = 1; j <= c; j++) {
rem[i][v] = c - j + c * (v >= N);
v = graph[v];
}
assert(v == graph[P + i * N]);
}
}
// set everything out of cycle
for (int i = 0; i < 2; i++) {
int target = P + i * N;
for (int u = 1; u <= 2 * N; u++) {
if (rem[i][u] != 0 || u == target) continue;
int v = u;
int d = 0;
do {
rem[i][v] = -1;
d++;
v = graph[v];
} while (rem[i][v] == 0 && v != target);
if (v == target) {
assert(rem[i][target] == -1 || rem[i][target] == 0);
for (v = u; v != graph[target]; v = graph[v])
rem[i][v] = d--;
assert(d == -1);
assert(rem[i][target] == 0);
} else if (rem[i][v] > 0) {
for (int w = u; w != v; w = graph[w])
rem[i][w] = rem[i][v] + d--;
assert(d == 0);
}
}
}
for (int i = 0; i < Q; i++) {
int res = 0;
for (int j = 0; j < 2; j++) {
for (int k = 1; k <= 2 * N; k++) {
if (rem[j][k] == -1) continue;
res += rem[j][k] <= G[i] && G[i] % cyc[j] == rem[j][k];
}
}
answer(res);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
