#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 300069;
int up[N], vis[N], n, nxt[N], deg[N], dep[N], sz[N];
vector<int> t[N];
void dfs(int v) {
vis[v] = 1;
if (t[t[v][0]][0] == v && (int)t[t[v][0]].size() > 1)
nxt[v] = n + t[v][0], deg[n + t[v][0]]++;
else
nxt[v] = t[v][0], deg[t[v][0]]++;
if (t[v].size() > 1) {
if (t[t[v][1]][0] == v && (int)t[t[v][1]].size() > 1)
nxt[n + v] = n + t[v][1], deg[n + t[v][1]]++;
else
nxt[n + v] = t[v][1], deg[t[v][1]]++;
}
for (auto u : t[v]) {
if (!vis[u])
dfs(u);
}
}
void count_routes(int n1, int m, int p, int r[][2], int q, int k[])
{
++p;
n = n1;
for (int i = 0;i < m;i++) {
r[i][0]++, r[i][1]++;
t[r[i][0]].push_back(r[i][1]);
t[r[i][1]].push_back(r[i][0]);
}
for (int i = 1;i <= n;i++) {
if (!vis[i])
dfs(i);
}
fill(vis, vis + 2 * n + 1, 0);
queue<int> que;
for (int i = 1;i <= 2 * n;i++) {
if (deg[i] == 0)
que.push(i);
}
vector<int> ord;
while (!que.empty()) {
auto v = que.front();
que.pop();
ord.push_back(v);
vis[v] = 1;
deg[nxt[v]]--;
if (deg[nxt[v]] == 0) {
dep[nxt[v]] = dep[v] + 1;
que.push(nxt[v]);
}
}
for (int i = 1;i <= 2 * n;i++) {
if (!vis[i]) {
int t = i, s = 0;
vector<int> o;
while (t > 0 && !vis[t]) {
vis[t] = 1;
up[t] = t;
o.push_back(t);
++s;
dep[nxt[t]] = dep[t] + 1;
t = nxt[t];
}
for (auto u : o)
sz[u] = s;
}
}
fill(vis, vis + 2 * n + 1, 0);
for (auto u : ord) {
if (vis[u])
continue;
function<int(int)> dfs = [&](int v) {
if (vis[v] || up[v] > 0)
return up[v];
vis[v] = 1;
if (nxt[v] > 0)
return up[v] = dfs(nxt[v]);
};
dfs(u);
}
for (int i = 0;i < q;i++) {
int ans = 0;
for (int j = 1;j <= n;j++) {
auto Try = [&](int p) {
if (up[j] == up[p]) {
int t = j, d = 0;
while (up[t] != t && t != p) {
if (nxt[t] == 0)
break;
t = nxt[t];
d++;
}
return (d == k[i] && t == p);
}
else if (up[j] != up[p] && up[p] == p) {
int t = j, d = 0;
while (up[t] != t) {
if (nxt[t] == 0)
break;
t = nxt[t];
d++;
}
int x = k[i] - d;
x %= sz[t];
if (dep[t] < dep[p])
return dep[p] - dep[t] == x;
return sz[t] - dep[t] + dep[p] == x;
}
return false;
};
ans += (Try(p) || Try(n + p));
}
answer(ans);
}
}
Compilation message
garden.cpp: In lambda function:
garden.cpp:83:7: warning: control reaches end of non-void function [-Wreturn-type]
83 | };
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
