#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
using namespace std::placeholders;
#define llong long long
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
// return (T)(rng() % range);
// }
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
const int inf = 2 * N + 10;
vector<int> next_node(N * 2, -1);
rep(i, M)
rep(f, 2) {
int u = R[i][f], v = R[i][!f];
bool v_prio = next_node[v << 1] == -1;
if (next_node[u << 1] == -1)
next_node[u << 1] = v << 1 | v_prio;
else if (next_node[u << 1 | 1] == -1)
next_node[u << 1 | 1] = v << 1 | v_prio;
}
rep(i, N) {
if (next_node[i << 1] == -1) continue;
if (next_node[i << 1 | 1] != -1) continue;
next_node[i << 1 | 1] = next_node[i << 1] & ~1;
if (next_node[next_node[i << 1 | 1]] / 2 == i)
next_node[i << 1 | 1] |= 1;
// clog << i << ' ' << next_node[i << 1 | 1] << endl;
}
// rep(i, N) {
// clog << i << ": ";
// rep(f, 2) clog << next_node[i << 1 | f] / 2 << "(" << next_node[i << 1 | f] % 2 << "); ";
// clog << endl;
// }
vector<vector<int>> gr(2 * N);
rep(i, 2 * N) {
if (next_node[i] == -1) continue;
gr[next_node[i]].emplace_back(i);
// clog << next_node[i] << ' ' << i << endl;
}
auto bfs = [&](int root) -> vector<int> {
vector<int> dis(2 * N, -1);
queue<int> qu;
for (qu.push(root), dis[root] = 0; len(qu); qu.pop()) {
int u = qu.front();
for (auto v: gr[u]) {
if (dis[v] != -1) continue;
dis[v] = dis[u] + 1;
qu.push(v);
}
}
return dis;
};
vector<int> dis_to_p[2];
int cycle_length[2] = {inf, inf};
rep(i, 2) {
int u = P << 1 | i;
dis_to_p[i] = bfs(u);
if (next_node[u] == -1) continue;
if (dis_to_p[i][next_node[u]] == -1) continue;
cycle_length[i] = dis_to_p[i][next_node[u]] - dis_to_p[i][u] + 1;
}
vector<vector<int>> group[2];
rep(i, 2) {
group[i].resize(2 * N);
for (int v = 0; v < 2 * N; v += 2) {
int dis = dis_to_p[i][v];
if (dis == -1) continue;
group[i][dis % cycle_length[i]].emplace_back(dis);
}
for (auto& f: group[i])
sort(f.begin(), f.end());
}
rep(i, Q) {
int ans = 0;
int query = G[i];
rep(f, 2) {
if (cycle_length[f] >= inf) {
if (query >= inf) continue;
ans += len(group[f][query]);
} else {
auto& cur_group = group[f][query % cycle_length[f]];
auto iter = upper_bound(cur_group.begin(), cur_group.end(), query);
ans += (int)(iter - cur_group.begin());
}
}
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
