#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, p;
vector<int> adj[150005];
vector<int> sadj[300005];
int v[300005], s[300005], cnt[300005];
int vn, sn;
stack<int> st;
int dfs(int now) {
int ret = v[now] = vn++;
st.push(now);
for (auto &there : sadj[now]) {
if (v[there] == -1)
ret = min(ret, dfs(there));
else if (s[there] == -1)
ret = min(ret, v[there]);
}
if (ret == v[now]) {
while (true) {
int temp = st.top();
st.pop();
s[temp] = sn;
cnt[sn]++;
if (temp == now)break;
}
sn++;
}
return ret;
}
vector<int> dist[2][300005];
int trip[300005];
void bfs(int st, int mode) {
int k = cnt[s[st]];
memset(trip, -1, sizeof(trip));
queue<int> q;
q.push(st);
trip[st] = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
if (now % 2 == 0)dist[mode][k == 1 ? trip[now] : trip[now] % k].push_back(trip[now]);
for (auto &there : sadj[now]) {
if (trip[there] == -1) {
trip[there] = trip[now] + 1;
q.push(there);
}
}
}
}
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]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
for (int now = 0; now < n; now++) {
int there = adj[now][0];
int u = now * 2;
int v = there * 2 + (adj[there].size() > 1 && adj[there][0] == now);
sadj[v].push_back(u);
if (adj[now].size() > 1) {
there = adj[now][1];
int u = now * 2 + 1;
int v = there * 2 + (adj[there].size() > 1 && adj[there][0] == now);
sadj[v].push_back(u);
}
}
memset(v, -1, sizeof(v));
memset(s, -1, sizeof(s));
for (int i = 0; i < n * 2; i++)
if (v[i] == -1)dfs(i);
for (int i = 0; i < 2; i++)
bfs(p * 2 + i, i);
for (int i = 0; i < Q; i++) {
int ans = 0;
for (int j = 0; j < 2; j++) {
int st = p * 2 + j;
int k = cnt[s[st]];
if (k == 1) {
if(G[i]<300005)
ans += dist[j][G[i]].size();
}
else {
ans += dist[j][G[i] % k].end() - lower_bound(dist[j][G[i] % k].begin(), dist[j][G[i] % k].end(), G[i]);
}
}
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
28644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
28644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
28644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
