#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx2,avx,sse,sse2,ssse3,tune=native,popcnt")
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 300500, mlg = 30;
int up[mlg][maxn], cnt[maxn];
void count_routes(int n, int m, int P, int R[][2], int Q, int G[]) {
memset(cnt, 0, sizeof cnt);
memset(up, -1, sizeof up);
for(int i = 0; i < m; i++) {
int f = R[i][0], t = R[i][1];
if(cnt[f] < 2) up[0][2*f + cnt[f]] = 2*t + (cnt[t]==0);
if(cnt[t] < 2) up[0][2*t + cnt[t]] = 2*f + (cnt[f]==0);
cnt[f]++, cnt[t]++;
}
for(int i = 0; i < 2*n; i++) if(up[0][i] < 0) up[0][i] = up[0][i^1];
for(int i = 1; i < mlg; i++)
for(int j = 0; j < 2*n; j++)
up[i][j] = up[i-1][up[i-1][j]];
for(int I = 0; I < Q; I++) {
int ans = 0;
for(int i = 0; i < 2*n; i+=2) cnt[i] = i;
for(int i = 0; i < mlg; i++)
if((G[I]>>i)&1)
for(int j = 0; j < 2*n; j+=2)
cnt[j] = up[i][cnt[j]];
for(int i = 0; i < 2*n; i+=2) ans += cnt[i] == 2*P || cnt[i] == 2*P+1;
answer(ans);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
36864 KB |
Output is correct |
2 |
Correct |
23 ms |
36864 KB |
Output is correct |
3 |
Correct |
24 ms |
36864 KB |
Output is correct |
4 |
Correct |
25 ms |
36736 KB |
Output is correct |
5 |
Correct |
23 ms |
36736 KB |
Output is correct |
6 |
Correct |
24 ms |
36864 KB |
Output is correct |
7 |
Correct |
23 ms |
36864 KB |
Output is correct |
8 |
Correct |
23 ms |
36864 KB |
Output is correct |
9 |
Correct |
25 ms |
36992 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
36864 KB |
Output is correct |
2 |
Correct |
23 ms |
36864 KB |
Output is correct |
3 |
Correct |
24 ms |
36864 KB |
Output is correct |
4 |
Correct |
25 ms |
36736 KB |
Output is correct |
5 |
Correct |
23 ms |
36736 KB |
Output is correct |
6 |
Correct |
24 ms |
36864 KB |
Output is correct |
7 |
Correct |
23 ms |
36864 KB |
Output is correct |
8 |
Correct |
23 ms |
36864 KB |
Output is correct |
9 |
Correct |
25 ms |
36992 KB |
Output is correct |
10 |
Correct |
23 ms |
36736 KB |
Output is correct |
11 |
Correct |
30 ms |
36992 KB |
Output is correct |
12 |
Correct |
39 ms |
37248 KB |
Output is correct |
13 |
Correct |
49 ms |
37496 KB |
Output is correct |
14 |
Correct |
68 ms |
37880 KB |
Output is correct |
15 |
Correct |
71 ms |
37884 KB |
Output is correct |
16 |
Correct |
64 ms |
37880 KB |
Output is correct |
17 |
Correct |
66 ms |
37880 KB |
Output is correct |
18 |
Correct |
39 ms |
37248 KB |
Output is correct |
19 |
Correct |
69 ms |
37880 KB |
Output is correct |
20 |
Correct |
75 ms |
38008 KB |
Output is correct |
21 |
Correct |
65 ms |
37880 KB |
Output is correct |
22 |
Correct |
64 ms |
37884 KB |
Output is correct |
23 |
Correct |
73 ms |
38008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
36864 KB |
Output is correct |
2 |
Correct |
23 ms |
36864 KB |
Output is correct |
3 |
Correct |
24 ms |
36864 KB |
Output is correct |
4 |
Correct |
25 ms |
36736 KB |
Output is correct |
5 |
Correct |
23 ms |
36736 KB |
Output is correct |
6 |
Correct |
24 ms |
36864 KB |
Output is correct |
7 |
Correct |
23 ms |
36864 KB |
Output is correct |
8 |
Correct |
23 ms |
36864 KB |
Output is correct |
9 |
Correct |
25 ms |
36992 KB |
Output is correct |
10 |
Correct |
23 ms |
36736 KB |
Output is correct |
11 |
Correct |
30 ms |
36992 KB |
Output is correct |
12 |
Correct |
39 ms |
37248 KB |
Output is correct |
13 |
Correct |
49 ms |
37496 KB |
Output is correct |
14 |
Correct |
68 ms |
37880 KB |
Output is correct |
15 |
Correct |
71 ms |
37884 KB |
Output is correct |
16 |
Correct |
64 ms |
37880 KB |
Output is correct |
17 |
Correct |
66 ms |
37880 KB |
Output is correct |
18 |
Correct |
39 ms |
37248 KB |
Output is correct |
19 |
Correct |
69 ms |
37880 KB |
Output is correct |
20 |
Correct |
75 ms |
38008 KB |
Output is correct |
21 |
Correct |
65 ms |
37880 KB |
Output is correct |
22 |
Correct |
64 ms |
37884 KB |
Output is correct |
23 |
Correct |
73 ms |
38008 KB |
Output is correct |
24 |
Correct |
25 ms |
36864 KB |
Output is correct |
25 |
Correct |
386 ms |
37112 KB |
Output is correct |
26 |
Correct |
631 ms |
37240 KB |
Output is correct |
27 |
Correct |
2118 ms |
37624 KB |
Output is correct |
28 |
Correct |
3331 ms |
37880 KB |
Output is correct |
29 |
Correct |
3486 ms |
38008 KB |
Output is correct |
30 |
Correct |
2268 ms |
37924 KB |
Output is correct |
31 |
Correct |
1959 ms |
38008 KB |
Output is correct |
32 |
Correct |
719 ms |
37848 KB |
Output is correct |
33 |
Correct |
3525 ms |
38528 KB |
Output is correct |
34 |
Correct |
3669 ms |
38568 KB |
Output is correct |
35 |
Correct |
2486 ms |
38480 KB |
Output is correct |
36 |
Correct |
1900 ms |
38520 KB |
Output is correct |
37 |
Correct |
4184 ms |
38520 KB |
Output is correct |
38 |
Correct |
4853 ms |
38648 KB |
Output is correct |