#include "bits/stdc++.h"
#include "garden.h"
#include "gardenlib.h"
#define overload(a, b, c, d, ...) d
#define rep1(a) for (ll _ = 0; _ < (ll)a; ++_)
#define rep2(i, a) for (ll i = 0; i < (ll)(a); ++i)
#define rep3(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) overload(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(i, a) for (ll i = (ll)(a) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (ll i = (ll)(b) - 1; i >= (ll)(a); --i)
#define rrep(...) overload(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
template <typename T, typename U>
inline bool chmin(T& a, const U& b) { return (a > b ? a = b, true : false); }
template <typename T, typename U>
inline bool chmax(T& a, const U& b) { return (a < b ? a = b, true : false); }
void count_routes(int n, int m, int p, int r[][2], int q, int query[]) {
vector<int> to(2 * n, -1);
vector<int> cnt(n);
vector<int> deg(n);
rep(i, m) {
deg[r[i][0]]++, deg[r[i][1]]++;
}
rep(i, m) {
int u = r[i][0], v = r[i][1];
if (to[u] == -1)
to[u] = ((deg[v] > 1 && to[v] == -1) ? v + n : v);
else if (to[u + n] == -1)
to[u + n] = ((deg[v] > 1 && to[v] == -1) ? v + n : v);
if (to[v] == -1)
to[v] = ((deg[u] > 1 && to[u] == v + n) ? u + n : u);
else if (to[v + n] == -1)
to[v + n] = ((deg[u] > 1 && to[u] == v) ? u + n : u);
}
// rep(i,n)if(to[i+n]==-1)to[i+n]=to[i];
vector<int> dist1(2 * n, 2e9), dist2(2 * n, 2e9);
vector<vector<int>> rg(2 * n);
rep(i, 2 * n) if (to[i] != -1) rg[to[i]].eb(i);
{
queue<int> que;
que.emplace(p);
dist1[p] = 0;
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto u : rg[v])
if (dist1[u] > dist1[v] + 1) {
dist1[u] = dist1[v] + 1;
que.emplace(u);
}
}
}
{
queue<int> que;
que.emplace(p + n);
dist2[p + n] = 0;
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto u : rg[v])
if (dist2[u] > dist2[v] + 1) {
dist2[u] = dist2[v] + 1;
que.emplace(u);
}
}
}
int cycle1 = 2e9, cycle2 = 2e9;
{
int now = p;
rep(i, 1, 2 * n + 1) {
now = to[now];
if (now == p) {
cycle1 = i;
break;
}
}
}
{
int now = p + n;
rep(i, 1, 2 * n + 1) {
now = to[now];
if (now == p + n) {
cycle2 = i;
break;
}
}
}
vector<vector<int>> f(cycle1), g(cycle2);
rep(i, n) {
f[dist1[i] % cycle1].eb(dist1[i]);
g[dist2[i] % cycle2].eb(dist2[i]);
}
rep(i, cycle1) sort(all(f[i]));
rep(i, cycle2) sort(all(g[i]));
rep(i, q) {
const int k = query[i];
int ans = upper_bound(all(f[k % cycle1]), k) - f[k % cycle1].begin();
ans += upper_bound(all(g[k % cycle2]), k) - g[k % cycle2].begin();
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
