#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 150069;
const int K = 30;
int up[2 * N][K], vis[N], n, nxt[2 * N], deg[2 * N];
vector<int> t[N];
void dfs(int v) {
vis[v] = 1;
if (t[t[v][0]][0] == v && (int)t[t[v][0]].size() > 1)
nxt[v] = n + t[v][0], deg[n + t[v][0]]++;
else
nxt[v] = t[v][0], deg[t[v][0]]++;
if (t[v].size() > 1) {
if (t[t[v][1]][0] == v && (int)t[t[v][1]].size() > 1)
nxt[n + v] = n + t[v][1], deg[n + t[v][1]]++;
else
nxt[n + v] = t[v][1], deg[t[v][1]]++;
}
for (auto u : t[v]) {
if (!vis[u])
dfs(u);
}
}
void count_routes(int n1, int m, int p, int r[][2], int q, int k[])
{
++p;
n = n1;
for (int i = 0;i < m;i++) {
r[i][0]++, r[i][1]++;
t[r[i][0]].push_back(r[i][1]);
t[r[i][1]].push_back(r[i][0]);
}
for (int i = 1;i <= n;i++) {
if (!vis[i])
dfs(i);
}
//graf ima 2 * N cvorova!
for (int i = 1;i <= 2 * n;i++)
up[i][0] = nxt[i];
for (int j = 1;j < K;j++) {
for (int i = 1;i <= 2 * n;i++) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
for (int i = 0;i < q;i++) {
int ans = 0;
for (int j = 1;j <= n;j++) {
int d = j;
for (int l = 0;l < K;l++) {
if (k[i] >> l & 1)
d = up[d][l];
if (d == 0)
break;
}
ans += (d == p || d == n + p);
}
answer(ans);
}
}
/*
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
2
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
1 2
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10844 KB |
Output is correct |
2 |
Correct |
2 ms |
10844 KB |
Output is correct |
3 |
Correct |
2 ms |
10844 KB |
Output is correct |
4 |
Correct |
2 ms |
10876 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
2 ms |
10844 KB |
Output is correct |
7 |
Correct |
2 ms |
10844 KB |
Output is correct |
8 |
Correct |
2 ms |
10840 KB |
Output is correct |
9 |
Correct |
4 ms |
10844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10844 KB |
Output is correct |
2 |
Correct |
2 ms |
10844 KB |
Output is correct |
3 |
Correct |
2 ms |
10844 KB |
Output is correct |
4 |
Correct |
2 ms |
10876 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
2 ms |
10844 KB |
Output is correct |
7 |
Correct |
2 ms |
10844 KB |
Output is correct |
8 |
Correct |
2 ms |
10840 KB |
Output is correct |
9 |
Correct |
4 ms |
10844 KB |
Output is correct |
10 |
Correct |
2 ms |
10844 KB |
Output is correct |
11 |
Correct |
11 ms |
15920 KB |
Output is correct |
12 |
Correct |
22 ms |
21040 KB |
Output is correct |
13 |
Correct |
63 ms |
35980 KB |
Output is correct |
14 |
Correct |
107 ms |
46628 KB |
Output is correct |
15 |
Correct |
113 ms |
47000 KB |
Output is correct |
16 |
Correct |
74 ms |
36380 KB |
Output is correct |
17 |
Correct |
61 ms |
32148 KB |
Output is correct |
18 |
Correct |
22 ms |
20824 KB |
Output is correct |
19 |
Correct |
107 ms |
46420 KB |
Output is correct |
20 |
Correct |
105 ms |
46932 KB |
Output is correct |
21 |
Correct |
81 ms |
36436 KB |
Output is correct |
22 |
Correct |
62 ms |
32084 KB |
Output is correct |
23 |
Correct |
120 ms |
48768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10844 KB |
Output is correct |
2 |
Correct |
2 ms |
10844 KB |
Output is correct |
3 |
Correct |
2 ms |
10844 KB |
Output is correct |
4 |
Correct |
2 ms |
10876 KB |
Output is correct |
5 |
Correct |
2 ms |
10844 KB |
Output is correct |
6 |
Correct |
2 ms |
10844 KB |
Output is correct |
7 |
Correct |
2 ms |
10844 KB |
Output is correct |
8 |
Correct |
2 ms |
10840 KB |
Output is correct |
9 |
Correct |
4 ms |
10844 KB |
Output is correct |
10 |
Correct |
2 ms |
10844 KB |
Output is correct |
11 |
Correct |
11 ms |
15920 KB |
Output is correct |
12 |
Correct |
22 ms |
21040 KB |
Output is correct |
13 |
Correct |
63 ms |
35980 KB |
Output is correct |
14 |
Correct |
107 ms |
46628 KB |
Output is correct |
15 |
Correct |
113 ms |
47000 KB |
Output is correct |
16 |
Correct |
74 ms |
36380 KB |
Output is correct |
17 |
Correct |
61 ms |
32148 KB |
Output is correct |
18 |
Correct |
22 ms |
20824 KB |
Output is correct |
19 |
Correct |
107 ms |
46420 KB |
Output is correct |
20 |
Correct |
105 ms |
46932 KB |
Output is correct |
21 |
Correct |
81 ms |
36436 KB |
Output is correct |
22 |
Correct |
62 ms |
32084 KB |
Output is correct |
23 |
Correct |
120 ms |
48768 KB |
Output is correct |
24 |
Correct |
6 ms |
10844 KB |
Output is correct |
25 |
Correct |
1948 ms |
15888 KB |
Output is correct |
26 |
Correct |
3938 ms |
21012 KB |
Output is correct |
27 |
Execution timed out |
5019 ms |
36956 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |