#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int max_N = 500005;
int n, m, p, cnt;
vi adj[max_N], g[max_N], gr[max_N];
pii edge[max_N], E[max_N];
map <pii, int> ind;
int used[max_N], par[max_N], cyc[max_N];
vi vec;
void dfs(int v) {
used[v] = 1;
for (int to : g[v]) {
if (used[to] == 1) {
vec.clear();
int u = v, len = 1;
while (u != to) {
vec.pb(u);
len++;
u = par[u];
}
vec.pb(to);
for (int i : vec) {
if (E[i].F == p) {
cyc[E[i].S] = len;
}
}
}
if (used[to] == 0) {
par[to] = v;
dfs(to);
}
}
used[v] = 2;
}
queue <int> q;
int dist[max_N], num[max_N], zero[max_N];
void bfs() {
while (!q.empty()) {
int v = q.front();
q.pop();
for (int to : gr[v]) {
if (!used[to]) {
used[to] = 1;
dist[to] = dist[v] + 1;
num[to] = num[v];
q.push(to);
}
}
}
}
int get(int k) {
int res = 0;
for (int i = 0; i < n; i++) {
if (i == p) {
continue;
}
int d = dist[zero[i]];
if (d == 0) {
continue;
}
int c = cyc[num[zero[i]]];
if ((c == 0 && k == d) || (c != 0 && k >= d && (k - d) % c == 0)) {
res++;
}
}
return res;
}
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++) {
adj[R[i][0]].pb(i + 1);
adj[R[i][1]].pb(i + 1);
edge[i + 1] = {R[i][0], R[i][1]};
}
for (int i = 0; i < n; i++) {
E[cnt] = {i, 0};
ind[{i, 0}] = cnt++;
for (int j : adj[i]) {
E[cnt] = {i, j};
ind[{i, j}] = cnt++;
}
}
for (int i = 0; i < n; i++) {
int to = edge[adj[i][0]].F + edge[adj[i][0]].S - i;
g[ind[{i, 0}]].pb(ind[{to, adj[i][0]}]);
for (int j : adj[i]) {
if (j == adj[i][0]) {
int tmp = 0;
if ((int)adj[i].size() > 1) {
tmp = 1;
}
to = edge[adj[i][tmp]].F + edge[adj[i][tmp]].S - i;
g[ind[{i, j}]].pb(ind[{to, adj[i][tmp]}]);
} else {
to = edge[adj[i][0]].F + edge[adj[i][0]].S - i;
g[ind[{i, j}]].pb(ind[{to, adj[i][0]}]);
}
}
}
for (int i = 0; i < cnt; i++) {
if (used[i] == 0) {
par[i] = -1;
dfs(i);
}
}
for (int i = 0; i < cnt; i++) {
for (int j : g[i]) {
gr[j].pb(i);
}
}
memset(& used, 0, sizeof(used));
for (int i : adj[p]) {
int v = ind[{p, i}];
used[v] = 1;
num[v] = i;
q.push(v);
}
bfs();
for (int i = 0; i < cnt; i++) {
if (E[i].S == 0) {
zero[E[i].F] = i;
}
}
for (int i = 0; i < Q; i++) {
answer(get(G[i]));
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
38016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
38016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
38016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
