#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "garden.h"
#include "gardenlib.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 3e5 + 10;
vector <pair <int, int>> e[N];
vector <int> adj[N];
int to[N], root[N], deg[N], pos[N];
int in[N], out[N], comp[N];
int d[N], sz[N], flag[N];
int IsAnc(int u, int v) {
return in[u] <= in[v] && out[v] <= out[u];
}
//void answer(int x) {
// cout << x << '\n';
//}
void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
vector <pair <int, int>> edges;
for (int i = 0; i < m; ++i) {
e[r[i][0]].push_back({r[i][1], i << 1});
e[r[i][1]].push_back({r[i][0], i << 1 ^ 1});
edges.push_back({r[i][0], r[i][1]});
edges.push_back({r[i][1], r[i][0]});
}
memset(root, -1, sizeof(root));
for (int i = 0; i < m * 2; ++i) {
auto [u, v] = edges[i];
to[i] = -1;
for (auto [w, j]: e[v]) {
if (i / 2 == j / 2) continue;
to[i] = j;
break;
}
if (to[i] == -1) to[i] = e[v][0].second;
}
for (int i = 0; i < m * 2; ++i) ++deg[to[i]];
queue <int> Q;
for (int i = 0; i < m * 2; ++i)
if (!deg[i]) Q.push(i);
while (Q.size()) {
int v = Q.front();
Q.pop();
flag[v] = 1;
int u = to[v];
adj[u].push_back(v);
if (!--deg[u]) Q.push(u);
}
int ti = 0, cnt = 0;
function <void(int)> dfs = [&](int u) {
in[u] = ++ti;
comp[u] = cnt;
if (d[u] == 0) root[u] = u;
for (auto v: adj[u]) {
root[v] = root[u];
d[v] = d[u] + 1;
dfs(v);
}
out[u] = ti;
};
// cout << edges[9].first << ' ' << edges[9].second << "sdfdsf\n";
// for (int i = 0; i < m * 2; ++i) cout << adj[i].size() << ' ';
// for (int i = 0; i < m * 2; ++i) cout << to[i] << ' ';
// cout << '\n';
for (int u = 0; u < m * 2; ++u) {
if (flag[u] || comp[u]) continue;
int v = u;
++cnt;
int num = 0;
// cout << u << "aa\n";
do {
pos[v] = num++;
dfs(v);
v = to[v];
} while (u != v);
do {
sz[v] = num;
v = to[v];
} while (u != v);
}
vector <int> fin;
for (int i = 0; i < e[p].size(); ++i) {
fin.push_back(e[p][i].second);
if (i == 1) break;
}
for (int r = 0; r < n; ++r) {
int i = e[r][0].second;
s[comp[i]].push_back(i);
}
for (int id = 0; id < q; ++id) {
int x = g[id];
int ans = 0;
for (auto v: fin) {
for (auto u: s[comp[v]]) {
if (flag[u] && flag[v]) {
if (IsAnc(v, u) && (d[u] - d[v] == x)) ++ans;
} else {
if (flag[v]) continue;
int y = x - d[u];
if (y < 0) continue;
int w = root[u];
int T = pos[v] - pos[w];
if (T < 0) T += sz[v];
if (y % sz[v] == T) ++ans;
}
}
}
answer(ans);
}
}
//
//int main() {
// int n, m, p;
// cin >> n >> m >> p;
// int r[m][2];
// for (int i = 0; i < m; ++i) {
// int u, v;
// cin >> u >> v;
// r[i][0] = u, r[i][1] = v;
// }
// int q;
// cin >> q;
// int g[q];
// for (int i = 0; i < q; ++i) cin >> g[i];
// count_routes(n, m, p, r, q, g);
//}
Compilation message
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
40 | auto [u, v] = edges[i];
| ^
garden.cpp:42:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for (auto [w, j]: e[v]) {
| ^
garden.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 0; i < e[p].size(); ++i) {
| ~~^~~~~~~~~~~~~
garden.cpp:100:9: error: 's' was not declared in this scope
100 | s[comp[i]].push_back(i);
| ^
garden.cpp:106:26: error: 's' was not declared in this scope
106 | for (auto u: s[comp[v]]) {
| ^
