//testing
#include "garden.h"
#include "gardenlib.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int deg[150010], Mn[150010], F[300010], D[300010], n, Res[2010];
bool v[300010];
vector<int> E[300010];
void DFS(int a, int d){
int i;
D[a] = d;
for (i = 0; i < E[a].size(); i++){
if (D[E[a][i]] == -1) DFS(E[a][i], d + 1);
}
}
int QQ, DD[300010];
struct Query{
int a, num;
bool operator < (const Query &p) const {
return a < p.a;
}
} w[2010];
int S[300010];
void Do(int a){
int i, x, c = 0, cnt = 0, pv;
for (i = 0; i < 2 * n; i++){
D[i] = -1;
v[i] = false;
S[i] = 0;
}
DFS(a, 0);
for (i = 0; i < n; i++){
if (D[i] != -1){
DD[cnt++] = D[i];
}
}
sort(DD, DD + cnt);
x = a;
while (!v[x]){
c++;
v[x] = true;
x = F[x];
}
if (x != a){
c = 1000000009;
}
pv = 0;
for (i = 0; i < QQ; i++){
while (pv < cnt && DD[pv] <= w[i].a){
S[DD[pv] % c]++;
pv++;
}
if (w[i].a % c > 2 * n)continue;
Res[w[i].num] += S[w[i].a % c];
}
}
void Add(int a, int b, int i){
if (Mn[a] == i){
if (Mn[b] != i || deg[b] == 1) F[a] = b;
else F[a] = b + n;
}
else if (F[a + n] == -1){
if (Mn[b] != i || deg[b] == 1) F[a + n] = b;
else F[a + n] = b + n;
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
int i, a, b;
n = N;
QQ = Q;
for (i = 0; i < Q; i++){
w[i].a = G[i];
w[i].num = i;
}
sort(w, w + Q);
for (i = 0; i < 2 * N; i++) F[i] = -1;
for (i = 0; i < M; i++){
a = R[i][0], b = R[i][1];
deg[a]++, deg[b]++;
if (!Mn[a]) Mn[a] = i + 1;
if (!Mn[b]) Mn[b] = i + 1;
}
for (i = 0; i < M; i++){
a = R[i][0], b = R[i][1];
Add(a, b, i+1);
Add(b, a, i+1);
}
for (i = 0; i < N; i++){
E[F[i]].push_back(i);
if (deg[i] > 1) E[F[i + N]].push_back(i + N);
}
Do(P);
if (deg[P] != 1) Do(P + N);
for (i = 0; i < Q; i++) answer(Res[i]);
}
Compilation message
garden.cpp: In function 'void DFS(int, int)':
garden.cpp:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for (i = 0; i < E[a].size(); i++){
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
7504 KB |
Output is correct |
2 |
Correct |
5 ms |
7488 KB |
Output is correct |
3 |
Correct |
5 ms |
7472 KB |
Output is correct |
4 |
Correct |
5 ms |
7676 KB |
Output is correct |
5 |
Correct |
6 ms |
7504 KB |
Output is correct |
6 |
Correct |
5 ms |
7504 KB |
Output is correct |
7 |
Correct |
5 ms |
7676 KB |
Output is correct |
8 |
Correct |
7 ms |
7504 KB |
Output is correct |
9 |
Correct |
6 ms |
7588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
7504 KB |
Output is correct |
2 |
Correct |
5 ms |
7488 KB |
Output is correct |
3 |
Correct |
5 ms |
7472 KB |
Output is correct |
4 |
Correct |
5 ms |
7676 KB |
Output is correct |
5 |
Correct |
6 ms |
7504 KB |
Output is correct |
6 |
Correct |
5 ms |
7504 KB |
Output is correct |
7 |
Correct |
5 ms |
7676 KB |
Output is correct |
8 |
Correct |
7 ms |
7504 KB |
Output is correct |
9 |
Correct |
6 ms |
7588 KB |
Output is correct |
10 |
Correct |
5 ms |
7504 KB |
Output is correct |
11 |
Correct |
11 ms |
9552 KB |
Output is correct |
12 |
Correct |
19 ms |
11088 KB |
Output is correct |
13 |
Correct |
47 ms |
25416 KB |
Output is correct |
14 |
Correct |
62 ms |
19272 KB |
Output is correct |
15 |
Correct |
67 ms |
19528 KB |
Output is correct |
16 |
Correct |
52 ms |
16968 KB |
Output is correct |
17 |
Correct |
55 ms |
15724 KB |
Output is correct |
18 |
Correct |
18 ms |
11120 KB |
Output is correct |
19 |
Correct |
46 ms |
19028 KB |
Output is correct |
20 |
Correct |
62 ms |
19872 KB |
Output is correct |
21 |
Correct |
51 ms |
16788 KB |
Output is correct |
22 |
Correct |
55 ms |
15544 KB |
Output is correct |
23 |
Correct |
50 ms |
20316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
7504 KB |
Output is correct |
2 |
Correct |
5 ms |
7488 KB |
Output is correct |
3 |
Correct |
5 ms |
7472 KB |
Output is correct |
4 |
Correct |
5 ms |
7676 KB |
Output is correct |
5 |
Correct |
6 ms |
7504 KB |
Output is correct |
6 |
Correct |
5 ms |
7504 KB |
Output is correct |
7 |
Correct |
5 ms |
7676 KB |
Output is correct |
8 |
Correct |
7 ms |
7504 KB |
Output is correct |
9 |
Correct |
6 ms |
7588 KB |
Output is correct |
10 |
Correct |
5 ms |
7504 KB |
Output is correct |
11 |
Correct |
11 ms |
9552 KB |
Output is correct |
12 |
Correct |
19 ms |
11088 KB |
Output is correct |
13 |
Correct |
47 ms |
25416 KB |
Output is correct |
14 |
Correct |
62 ms |
19272 KB |
Output is correct |
15 |
Correct |
67 ms |
19528 KB |
Output is correct |
16 |
Correct |
52 ms |
16968 KB |
Output is correct |
17 |
Correct |
55 ms |
15724 KB |
Output is correct |
18 |
Correct |
18 ms |
11120 KB |
Output is correct |
19 |
Correct |
46 ms |
19028 KB |
Output is correct |
20 |
Correct |
62 ms |
19872 KB |
Output is correct |
21 |
Correct |
51 ms |
16788 KB |
Output is correct |
22 |
Correct |
55 ms |
15544 KB |
Output is correct |
23 |
Correct |
50 ms |
20316 KB |
Output is correct |
24 |
Correct |
6 ms |
7504 KB |
Output is correct |
25 |
Correct |
12 ms |
9552 KB |
Output is correct |
26 |
Correct |
22 ms |
11108 KB |
Output is correct |
27 |
Correct |
42 ms |
25628 KB |
Output is correct |
28 |
Correct |
52 ms |
19288 KB |
Output is correct |
29 |
Correct |
60 ms |
19784 KB |
Output is correct |
30 |
Correct |
61 ms |
16988 KB |
Output is correct |
31 |
Correct |
43 ms |
15688 KB |
Output is correct |
32 |
Correct |
19 ms |
11088 KB |
Output is correct |
33 |
Correct |
46 ms |
19272 KB |
Output is correct |
34 |
Correct |
83 ms |
19784 KB |
Output is correct |
35 |
Correct |
50 ms |
16712 KB |
Output is correct |
36 |
Correct |
53 ms |
15796 KB |
Output is correct |
37 |
Correct |
52 ms |
20308 KB |
Output is correct |
38 |
Correct |
65 ms |
32072 KB |
Output is correct |