#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#ifdef tabr
void answer(int n) {
cout << n << '\n';
}
#else
#include "garden.h"
#include "gardenlib.h"
#endif
void count_routes(int n, int m, int p, int r[][2], int q, int k[]) {
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
g[r[i][0]].emplace_back(r[i][1]);
g[r[i][1]].emplace_back(r[i][0]);
}
vector<vector<int>> nxt(30, vector<int>(2 * n));
for (int i = 0; i < n; i++) {
nxt[0][i] = g[i][0];
nxt[0][i + n] = (g[i].size() == 1 ? g[i][0] : g[i][1]);
if (g[nxt[0][i]][0] == i) {
nxt[0][i] += n;
}
if (g[nxt[0][i + n]][0] == i) {
nxt[0][i + n] += n;
}
}
for (int i = 1; i < 30; i++) {
for (int j = 0; j < 2 * n; j++) {
nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
}
}
for (int i = 0; i < q; i++) {
int ans = 0;
for (int j = 0; j < n; j++) {
int v = j;
for (int l = 29; l >= 0; l--) {
if (k[i] & (1 << l)) {
v = nxt[l][v];
}
}
if (v % n == p) {
ans++;
}
debug(v, j);
}
answer(ans);
}
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, p, q;
cin >> n >> m >> p >> q;
int r[100][2];
int k[100];
for (int i = 0; i < m; i++) {
cin >> r[i][0] >> r[i][1];
}
for (int i = 0; i < q; i++) {
cin >> k[i];
}
count_routes(n, m, p, r, q, k);
return 0;
}
#endif
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
568 KB |
Output is correct |
3 |
Correct |
1 ms |
552 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
568 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
4 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
568 KB |
Output is correct |
3 |
Correct |
1 ms |
552 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
568 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
4 ms |
844 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
13 ms |
7372 KB |
Output is correct |
12 |
Correct |
29 ms |
12628 KB |
Output is correct |
13 |
Correct |
41 ms |
27384 KB |
Output is correct |
14 |
Correct |
89 ms |
43436 KB |
Output is correct |
15 |
Correct |
98 ms |
43976 KB |
Output is correct |
16 |
Correct |
66 ms |
30708 KB |
Output is correct |
17 |
Correct |
59 ms |
26352 KB |
Output is correct |
18 |
Correct |
26 ms |
12612 KB |
Output is correct |
19 |
Correct |
103 ms |
43400 KB |
Output is correct |
20 |
Correct |
88 ms |
43968 KB |
Output is correct |
21 |
Correct |
67 ms |
30604 KB |
Output is correct |
22 |
Correct |
60 ms |
26348 KB |
Output is correct |
23 |
Correct |
93 ms |
47912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
568 KB |
Output is correct |
3 |
Correct |
1 ms |
552 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
568 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
4 ms |
844 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
13 ms |
7372 KB |
Output is correct |
12 |
Correct |
29 ms |
12628 KB |
Output is correct |
13 |
Correct |
41 ms |
27384 KB |
Output is correct |
14 |
Correct |
89 ms |
43436 KB |
Output is correct |
15 |
Correct |
98 ms |
43976 KB |
Output is correct |
16 |
Correct |
66 ms |
30708 KB |
Output is correct |
17 |
Correct |
59 ms |
26352 KB |
Output is correct |
18 |
Correct |
26 ms |
12612 KB |
Output is correct |
19 |
Correct |
103 ms |
43400 KB |
Output is correct |
20 |
Correct |
88 ms |
43968 KB |
Output is correct |
21 |
Correct |
67 ms |
30604 KB |
Output is correct |
22 |
Correct |
60 ms |
26348 KB |
Output is correct |
23 |
Correct |
93 ms |
47912 KB |
Output is correct |
24 |
Correct |
7 ms |
308 KB |
Output is correct |
25 |
Correct |
2195 ms |
7364 KB |
Output is correct |
26 |
Correct |
3949 ms |
12636 KB |
Output is correct |
27 |
Execution timed out |
5060 ms |
27360 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |