#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
#define all(x) x.begin(), x.end()
// void answer(int x) {
// cout << x << endl;
// }
void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
vvi adj(n);
vector<pair<int, int>> edges;
for (int i=0;i<m;i++) {
int u = r[i][0];
int v = r[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
edges.push_back({u, v});
edges.push_back({v, u});
}
vi fmax(n, -1);
vi smax(n, -1);
for (int i=0;i<n;i++) {
fmax[i] = adj[i][0];
if (adj[i].size() > 1) smax[i] = adj[i][1];
}
int E = (int)edges.size();
map<pair<int, int>, int> lookup;
for (int i=0;i<E;i++) {
lookup[edges[i]] = i;
}
vi succ(E, -1);
for (int i=0;i<E;i++) {
auto [u, v] = edges[i];
if (smax[v] == -1 || fmax[v] != u) succ[i] = lookup[{v, fmax[v]}];
else succ[i] = lookup[{v, smax[v]}];
}
int goal = lookup[{p, fmax[p]}];
int goal2 = -1;
if (smax[p] != -1) goal2 = lookup[{p, smax[p]}];
// get cycle length
auto get_clen = [&]() {
int baby = goal;
int giant = goal;
int ans = 0;
do {
baby = succ[baby];
giant = succ[succ[giant]];
ans++;
} while (baby != giant);
return ans;
};
int clen = get_clen();
auto check_in_cycle = [&](int v) {
int w = v;
for (int i=0;i<clen;i++) w = succ[w];
return w == v;
};
bool in_cycle = check_in_cycle(goal);
bool in_cycle2 = false;
if (goal2 != -1) in_cycle2 = check_in_cycle(goal2);
vvi radj(E);
for (int i=0;i<E;i++) radj[succ[i]].push_back(i);
auto get_closest = [&](int fin, bool cycle) {
vi dists(E, -1);
dists[fin] = 0;
queue<int> bfs;
bfs.push(fin);
while (!bfs.empty()) {
int cur = bfs.front(); bfs.pop();
for (int w : radj[cur]) {
if (dists[w] != -1) continue;
dists[w] = dists[cur] + 1;
bfs.push(w);
}
}
vi ans(E+1, 0);
for (int i=0;i<n;i++) {
int e = lookup[{i, fmax[i]}];
int d = dists[e];
if (d >= 0) ans[d]++;
}
if (cycle) {
for (int i=clen;i<=E;i++) ans[i] += ans[i-clen];
}
return ans;
};
vi sumfreq(E+1, 0);
vi freq1 = get_closest(goal, in_cycle);
for (int i=0;i<=E;i++) sumfreq[i] += freq1[i];
if (goal2 != -1) {
vi freq2 = get_closest(goal2, in_cycle2);
for (int i=0;i<=E;i++) sumfreq[i] += freq2[i];
}
auto do_query = [&](int k) {
if (k > E) {
k %= clen;
k += ((E - k)/clen) * clen;
}
return sumfreq[k];
};
vi G(g, g+q);
for (int k : G) {
answer(do_query(k));
}
}
// int main() {
// std::ios::sync_with_stdio(false);
// std::cin.tie(NULL);
// {
// int N = 6;
// int M = 6;
// int P = 0;
// int R[][2] = {
// {1, 2},
// {0, 1},
// {0, 3},
// {3, 4},
// {4, 5},
// {1, 5}
// };
// int Q = 1;
// int G[] = {3};
// count_routes(N, M, P, R, Q, G);
// }
// cout << "-----------" << endl;
// {
// int N = 5;
// int M = 5;
// int P = 2;
// int R[][2] = {
// {1, 0},
// {1, 2},
// {3, 2},
// {1, 3},
// {4, 2}
// };
// int Q = 2;
// int G[] = {3, 1};
// count_routes(N, M, P, R, Q, G);
// }
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
