#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int N = 150010;
const int INF = 2e9;
vector<int> mn[N], G[2*N];
int nxt[2*N], deg[2*N], h[2*N], ph[2*N];
bool comp[2*N][3];
void expand(int u, int c, int s, int d=0, int p=-INF)
{
if (comp[u][c])
return;
if (deg[u] != 1 && (u == 2*s || u == 2*s+1)) {
assert(p != 0);
p = 0;
}
h[u] = d, ph[u] = p;
comp[u][c] = true;
for (auto v : G[u])
expand(v, c, s, d+1, p+1);
}
void count_routes(int n, int m, int p, int R[][2], int q, int K[])
{
// find min and second-min
for (int i = 0; i < m; ++i) {
int u = R[i][0], v = R[i][1];
if (mn[u].size() < 2)
mn[u].push_back(v);
if (mn[v].size() < 2)
mn[v].push_back(u);
}
// completely second-min
for (int i = 0; i < n; ++i) {
if (mn[i].size() == 0) continue;
if (mn[i].size() == 1) mn[i].push_back(mn[i].back());
}
// find nxt of each node
for (int i = 0; i < n; ++i) {
if (mn[i].size() == 0) continue;
// normal node
int j = mn[i][0];
if (mn[j][0] != i) nxt[2*i] = 2*j;
else nxt[2*i] = 2*j+1;
// walked node
j = mn[i][1];
if (mn[j][0] != i) nxt[2*i+1] = 2*j;
else nxt[2*i+1] = 2*j+1;
}
// find degree and make reversed graph: G
for (int u = 0; u < 2*n; ++u) {
++deg[nxt[u]];
G[nxt[u]].push_back(u);
}
// find cycle
queue<int> Q;
for (int u = 0; u < 2*n; ++u) {
if (deg[u] == 0)
Q.push(u);
}
while (!Q.empty()) {
int u = Q.front();
Q.pop();
if (--deg[nxt[u]] == 0)
Q.push(nxt[u]);
}
// expand
expand(2*p, 1, p);
expand(2*p+1, 2, p);
// find cycle size for 2*p and 2*p+1 (just in case they're different)
int c1 = 0, u = 2*p;
if (deg[u] == 1) {
do {
++c1;
u = nxt[u];
} while (u != 2*p);
}
int c2 = 0;
u = 2*p+1;
if (deg[u] == 1) {
do {
++c2;
u = nxt[u];
} while (u != 2*p+1);
}
assert((c1 == 0) != (c2 == 0));
// answer each query
for (int i = 0; i < q; ++i) {
int k = K[i], cnt = 0;
for (int j = 0; j < n; ++j) {
int u = 2*j;
bool ans = ph[u] == K[i];
if (k-h[u] >= 0) {
if (comp[u][1] && c1 > 0)
ans |= (k-h[u])%c1 == 0;
if (comp[u][2] && c2 > 0)
ans |= (k-h[u])%c2 == 0;
}
if (ans) ++cnt;
}
answer(cnt);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
22392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
22392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
22392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
