#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int MXN = 1.5e5+5, INF = 1e9;
pii MinPath[MXN][2], rot[MXN][2];
int d[MXN][2], deg[MXN][2], pos[MXN][2], com[MXN][2];
bool iscycle[MXN][2];
vector<pii> g[MXN][2], rg[MXN][2];
vector<vector<pii> > comp;
void fill_tree(pii u, pii p, pii root) {
rot[u.x][u.y] = root, d[u.x][u.y] = d[p.x][p.y] + 1;
for(pii v : rg[u.x][u.y]) if(!iscycle[v.x][v.y] and v != p) fill_tree(v, u, root);
}
void count_routes(int N, int M, int P, int R[][2], int Qq, int G[]) {
fill(MinPath[0], MinPath[N-1] + 2, pii(INF, -1));
for(int i = 0; i < M; ++i) {
int u = R[i][0], v = R[i][1];
pii a(i, v), b(i, u);
if(MinPath[u][0] > a) swap(MinPath[u][0], a);
if(MinPath[u][1] > a) swap(MinPath[u][1], a);
if(MinPath[v][0] > b) swap(MinPath[v][0], b);
if(MinPath[v][1] > b) swap(MinPath[v][1], b);
}
for(int i = 0; i < N; ++i) {
if(MinPath[i][1].x == INF) MinPath[i][1] = MinPath[i][0];
g[i][0].emplace_back(MinPath[i][0].y, MinPath[MinPath[i][0].y][0].x == MinPath[i][0].x);
g[i][1].emplace_back(MinPath[i][1].y, MinPath[MinPath[i][1].y][0].x == MinPath[i][1].x);
}
// for(int i = 0; i < N; ++i) for(int j = 0; j < 2; ++j) printf("%d %d :: %d %d\n", i, j, g[i][j][0].x, g[i][j][0].y);
/***************************** find cycle *******************************/
for(int i = 0; i < N; ++i) {
for(auto x : g[i][0]) deg[x.x][x.y]++, rg[x.x][x.y].emplace_back(i, 0);
for(auto x : g[i][1]) deg[x.x][x.y]++, rg[x.x][x.y].emplace_back(i, 1);
}
queue<pii> Q;
for(int i = 0; i < N; ++i) {
if(!deg[i][0]) Q.emplace(i, 0);
if(!deg[i][1]) Q.emplace(i, 1);
}
while(!Q.empty()) {
pii now = Q.front(); Q.pop();
for(pii v : g[now.x][now.y]) if(deg[v.x][v.y] >= 1) {
deg[v.x][v.y]--;
if(!deg[v.x][v.y]) Q.emplace(v.x, v.y);
}
}
for(int i = 0; i < N; ++i) for(int j = 0; j < 2; ++j) {
if(deg[i][j] == 1) deg[i][j]--, Q.emplace(i, j);
else continue;
comp.emplace_back(vector<pii>());
while(!Q.empty()) {
pii now = Q.front(); Q.pop();
com[now.x][now.y] = comp.size()-1;
pos[now.x][now.y] = comp.back().size();
iscycle[now.x][now.y] = true;
comp.back().emplace_back(now.x, now.y);
for(pii v : g[now.x][now.y]) if(!--deg[v.x][v.y]) Q.emplace(v.x, v.y);
}
for(auto x : comp.back()) fill_tree(x, pii(MXN-1, 0), x);
}
/************************** end **************************************/
vector<int> dis[2];
auto Merge = [&](pii a, pii b) {
if(iscycle[b.x][b.y]) {
pii root = rot[a.x][a.y];
if(com[root.x][root.y] != com[b.x][b.y]) return;
int d_to_rot = d[a.x][a.y];
if(pos[root.x][root.y] <= pos[b.x][b.y]) d_to_rot += pos[b.x][b.y] - pos[root.x][root.y];
else d_to_rot += comp[com[b.x][b.y]].size() - (pos[root.x][root.y] - pos[b.x][b.y]);
dis[b.y].emplace_back(d_to_rot);
} else {
if(rot[a.x][a.y] != rot[b.x][b.y]) return;
int d_to_pos = d[a.x][a.y] - d[b.x][b.y];
if(d_to_pos >= 0) dis[b.y].emplace_back(d_to_pos);
}
};
for(int i = 0; i < N; ++i) for(int k = 0; k < 2; ++k) {
Merge(pii(i, 0), pii(P, k));
}
/*****************************************************************/
for(int i = 0; i < Qq; ++i) {
int len = G[i], sum = 0;
auto f = [&](bool st) {
for(int x : dis[st]) if(iscycle[P][st]) {
if(len - x >= 0 and ((len - x) % comp[com[P][st]].size()) == 0) sum++;
} else if(x == len) sum++;
};
f(0), f(1);
answer(sum);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
14732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
