This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
int n, m, fn;
vector<vector<pair<int, int>>> a;
vector<int> g;
vector<bool> vis;
vector<bool> start;
vector<bool> finish;
void dfs(int u, int p, int i) {
int x = (i << 1) + (p > u);
if (x >= 0 && vis[x]) return;
if (x != -1) vis[x] = 1;
if (a[u].size() == 0) return;
if (i != -1 && u == fn) finish[x] = 1;
int id = (a[u].size() == 1 || a[u][0].second != i) ? 0 : 1;
int v = a[u][id].first;
int j = a[u][id].second;
int y = (j << 1) + (v < u);
if (x != -1) {
if (g[x] != -1 && g[x] != y) exit(1);
g[x] = y;
}
else start[y] = 1;
dfs(v, u, j);
}
bool check(int u, int k) {
for (int i = 0; i < k - 1; i++) {
u = g[u];
if (u == -1) return 0;
}
return finish[u];
}
void count_routes(int N, int M, int P, int ed[][2], int q, int qry[]) {
n = N, m = (M << 1), fn = P;
a.resize(n);
vis.resize(m, 0);
g.resize(m, -1);
start.resize(m, 0);
finish.resize(m, 0);
for (int i = 0; i < M; i++) {
int u = ed[i][0], v = ed[i][1];
if (a[u].size() < 2) a[u].push_back({v, i});
if (a[v].size() < 2) a[v].push_back({u, i});
}
for (int u = 0; u < n; u++) {
dfs(u, n, -1);
}
for (int i = 0; i < q; i++) {
int ans = 0;
for (int u = 0; u < m; u++) {
if (start[u] && check(u, qry[i])) {
ans++;
}
}
answer(ans);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |