#include "gardenlib.h"
#include "garden.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 2e5+5;
int deg[N<<1], d[N<<1];
vector<pii> pre[N];
vector<int> g[N<<1];
void count_routes(int n, int m, int p, int r[][2], int q, int _g[]) {
fill_n(d, N<<1, 1e9+1);
for(int i = 0; i < m; i++) {
int a = r[i][0], b = r[i][1];
if(pre[a].size() < 2) pre[a].emplace_back(b, i);
if(pre[b].size() < 2) pre[b].emplace_back(a, i);
}
for(int i = 0; i < n; i++) if(pre[i].size() == 1) pre[i].emplace_back(pre[i][0]);
for(int i = 0; i < n; i++) for(int j = 0; j < (int)pre[i].size(); j++) {
int v = pre[i][j].x, id = pre[i][j].y;
if(pre[v][0].y == id) v += n;
g[v].emplace_back(i + (j ? n : 0));
++deg[i + (j ? n : 0)];
}
queue<int> Q;
for(int i = 0; i < 2*n; i++) if(!deg[i]) Q.emplace(i);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int v : g[u]) if(!--deg[v])
Q.emplace(v);
}
int cyc_sz = 0;
for(int i = 0; i < 2*n; i++) if(deg[i]) ++cyc_sz;
auto get_dist = [&](int a) {
vector<bool> chk(n<<1);
d[a] = 0, chk[a] = true;
Q.emplace(a);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int v : g[u]) if(!chk[v])
chk[v] = true, d[v] = d[u] + 1, Q.emplace(v);
}
};
auto get_ans = [&](int len) {
int ret = 0;
for(int i = 0; i < n; i++) {
if(d[i] > len) continue;
if(cyc_sz) ret += ((len % cyc_sz) == d[i]);
else ++ret;
}
return ret;
};
vector<int> ans(q, 0);
get_dist(p);
for(int i = 0; i < q; i++) ans[i] += get_ans(_g[i]);
get_dist(p + n);
for(int i = 0; i < q; i++) answer(ans[i] + get_ans(_g[i]));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
16120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
16120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
16120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
