#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <vector>
#define N 150001
#define MP 23
using namespace std;
int n, m, start, cycle1_len, cycle2_len;
int Sx, Sy, d[N][2], d1[N][2], d2[N][2];
pair<int, int> r[N];
void Push_r(int x, int y) {
if (!r[x].first) r[x].first = y;
else if (!r[x].second) r[x].second = y;
}
int dfs(int x, int y, int len) {
d[x][y] = len;
int nx = y ? r[x].second : r[x].first;
int ny = r[nx].second && r[nx].first == x ? 1 : 0;
if (d[nx][ny]) {
if (d[nx][ny] == 1) return len;
else return -1;
}
return dfs(nx, ny, len + 1);
}
int dfs_find1(int x, int y) {
if (x == start && y == 0) return 0;
if (d1[x][y] != 0) return d1[x][y];
int nx = y ? r[x].second : r[x].first;
int ny = r[nx].second && r[nx].first == x ? 1 : 0;
d1[x][y] = -1, d1[x][y] = dfs_find1(nx, ny);
if (d1[x][y] >= 0) d1[x][y]++;
return d1[x][y];
}
int dfs_find2(int x, int y) {
if (x == start && y == 1) return 0;
if (d2[x][y] != 0) return d2[x][y];
int nx = y ? r[x].second : r[x].first;
int ny = r[nx].second && r[nx].first == x ? 1 : 0;
d2[x][y] = -1, d2[x][y] = dfs_find2(nx, ny);
if (d2[x][y] >= 0) d2[x][y]++;
return d2[x][y];
}
void count_routes(int _n, int _m, int _s, int _r[][2], int Q_len, int Q[]) {
n = _n, start = _s + 1;
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);
}
cycle1_len = dfs(start, 0, 1);
for (int i = 1; i <= n; i++) d[i][0] = d[i][1] = 0;
cycle2_len = dfs(start, 1, 1);
for (int i = 1; i <= n; i++) d[i][0] = d[i][1] = 0;
for (int i = 1; i <= n; i++) {
if (d1[i][0] == 0) dfs_find1(i, 0);
if (d2[i][0] == 0) dfs_find2(i, 0);
}
for (int i = 0; i < Q_len; i++) {
int res = 0;
if (Q[i] == 0) { answer(1); continue; }
for (int j = 1; j <= n; j++) {
if (d1[j][0] == Q[i] || d2[j][0] == Q[i]) res++;
else if (d1[j][0] > 0 && cycle1_len > 0 && (Q[i] - d1[j][0]) % cycle1_len == 0) res++;
else if (d2[j][0] > 0 && cycle2_len > 0 && (Q[i] - d2[j][0]) % cycle2_len == 0) res++;
} answer(res);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
