#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <vector>
#define N 150001
using namespace std;
int n, m, start, p[30], R, Rw, tot;
bool check[N][2][30];
pair<int, int> r[N];
vector<int> r1[N], r2[N];
vector<pair<int, int> > d[N][2][30];
void Push_r(int x, int y) {
if (!r[x].first) r[x].first = y;
else if (!r[x].second) r[x].second = y;
}
void f(int x, int y, int s) {
if (s == 0 || check[x][y][s]) return;
f(x, y, s - 1), check[x][y][s] = true;
for (auto i : d[x][y][s - 1]) {
f(i.first, i.second, s - 1);
for (auto j : d[i.first][i.second][s - 1])
d[x][y][s].push_back(j);
}
}
void g(int x, int y, int R, int Rw) {
if (R == 0) {
if (y == 0 || r[x].first == 0) tot++;
return;
}
while (p[Rw] > R) Rw--;
f(x, y, Rw);
for (auto i : d[x][y][Rw]) g(i.first, i.second, R - p[Rw], Rw);
}
void count_routes(int _n, int _m, int _s, int _r[][2], int Q_len, int Q[]) {
if (_n >= 30) return;
n = _n, start = _s + 1, p[0] = 1;
for (int i = 1; i < 30; i++) p[i] = p[i - 1] * 2;
for (int i = 0; i < _m; i++) {
int x = _r[i][0] + 1, y = _r[i][1] + 1;
Push_r(x, y), Push_r(y, x);
}
for (int i = 1; i <= n; i++) {
if (!r[i].second) r[i].second = r[i].first, r[i].first = 0;
if (r[i].first) r1[r[i].first].push_back(i);
r2[r[i].second].push_back(i);
if (r[r[i].first].first == i || (r[r[i].first].first == 0 && r[r[i].first].second == i)) d[r[i].first][1][0].push_back({ i,0 });
if (r[r[i].second].first == i || (r[r[i].second].first == 0 && r[r[i].second].second == i)) d[r[i].second][1][0].push_back({ i,1 });
}
for (int i = 1; i <= n; i++) {
for (auto j : r1[i])
if (j != r[i].first && (r[i].first || r[i].second != j)) d[i][0][0].push_back({ j,0 });
for (auto j : r2[i])
if (j != r[i].first && (r[i].first || r[i].second != j)) d[i][0][0].push_back({ j,1 });
}
for (int i = 0; i < Q_len; i++) {
tot = 0, g(start, 0, Q[i], 29), g(start, 1, Q[i], 29);
answer(tot);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
218780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
218780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
218780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
