#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+2022LL;
vector <int> g[200010];
long long sz[200010],d[200010],ac[200010],n,dif;
long long weight[100010],a[100010],weightps[100010],seg[400040],laz[400010];
bool marked[100010];
void dfs1(int cur){
sz[cur]=g[cur].size();
sz[cur]=max(sz[cur],1LL);
sz[cur]%=mod;
for (int i:g[cur]){
dfs1(i);
sz[cur]=sz[cur]*sz[i]%mod;
}
if (!g[cur].size()){
return;
} else {
long long fr[g[cur].size()],ba[g[cur].size()];
for (int i=0; i<g[cur].size(); i++){
if (!i) fr[i]=sz[g[cur][i]]%mod;
else fr[i]=fr[i-1]*sz[g[cur][i]]%mod;
}
for (int i=g[cur].size()-1; i>=0; i--){
if (i==g[cur].size()-1) ba[i]=sz[g[cur][i]]%mod;
else ba[i]=ba[i+1]*sz[g[cur][i]]%mod;
}
for (int i=0; i<g[cur].size(); i++){
int t=1;
if (i) t=t*fr[i-1]%mod;
if (i+1<g[cur].size()) t=t*ba[i+1]%mod;
d[g[cur][i]]=t%mod;
}
}
}
void dfs2(int cur){
for (int i:g[cur]){
ac[i]=ac[cur]%mod*d[i]%mod;
dfs2(i);
}
}
void build(int id,int tl,int tr){
if (tl==tr){
seg[id]=a[tl]*weight[tl]%mod;
return;
}
int tm=(tl+tr)/2;
build(2*id,tl,tm);
build(2*id+1,tm+1,tr);
seg[id]=(seg[2*id]+seg[2*id+1])%mod;
}
void pushdown(int id,int tl,int tr){
if (!marked[id]) return;
int tm=(tl+tr)/2;
if (laz[id]%2==1){
seg[2*id]=(weightps[tm]-weightps[tl-1]+mod-seg[2*id]+mod)%mod;
seg[2*id+1]=(weightps[tr]-weightps[tm]+mod-seg[2*id+1]+mod)%mod;
}
marked[2*id]=1; laz[2*id]+=laz[id];
marked[2*id+1]=1; laz[2*id+1]+=laz[id];
marked[id]=0; laz[id]=0;
}
void update(int id,int tl,int tr,int l,int r){
if (l>r) return;
if (l<=tl&&tr<=r){
seg[id]=(weightps[tr]-weightps[tl-1]+mod-seg[id]+mod)%mod;
laz[id]++;
marked[id]=1;
return;
}
pushdown(id,tl,tr);
int tm=(tl+tr)/2;
update(2*id,tl,tm,l,min(r,tm));
update(2*id+1,tm+1,tr,max(tm+1,l),r);
seg[id]=(seg[2*id]+seg[2*id+1])%mod;
}
long long query(int id,int tl,int tr,int l,int r){
if (l>r) return 0;
if (l<=tl&&tr<=r) return seg[id];
pushdown(id,tl,tr);
int tm=(tl+tr)/2;
long long lx=query(2*id,tl,tm,l,min(r,tm));
long long rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
return (lx+rx)%mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=M; dif=N-1;
for (int i=1; i<N+M; i++) g[P[i]].push_back(i);
dfs1(0);
ac[0]=1;
dfs2(0);
for (int i=1; i<=n; i++) weight[i]=ac[i+N-1]%mod;
for (int i=1; i<=n; i++) weightps[i]=(weightps[i-1]+weight[i])%mod;
for (int i=1; i<=n; i++) a[i]=A[i-1];
build(1,1,n);
}
int count_ways(int L, int R) {
L-=dif; R-=dif;
update(1,1,n,L,R);
return query(1,1,n,1,n)%mod;
}
Compilation message
circuit.cpp: In function 'void dfs1(int)':
circuit.cpp:23:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i=0; i<g[cur].size(); i++){
| ~^~~~~~~~~~~~~~
circuit.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | if (i==g[cur].size()-1) ba[i]=sz[g[cur][i]]%mod;
| ~^~~~~~~~~~~~~~~~~
circuit.cpp:31:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i=0; i<g[cur].size(); i++){
| ~^~~~~~~~~~~~~~
circuit.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | if (i+1<g[cur].size()) t=t*ba[i+1]%mod;
| ~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
4944 KB |
Output is correct |
3 |
Correct |
3 ms |
5112 KB |
Output is correct |
4 |
Correct |
3 ms |
5072 KB |
Output is correct |
5 |
Correct |
3 ms |
5072 KB |
Output is correct |
6 |
Correct |
3 ms |
5060 KB |
Output is correct |
7 |
Correct |
3 ms |
5072 KB |
Output is correct |
8 |
Correct |
4 ms |
5140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
5072 KB |
Output is correct |
3 |
Correct |
4 ms |
5080 KB |
Output is correct |
4 |
Correct |
3 ms |
5072 KB |
Output is correct |
5 |
Correct |
4 ms |
5072 KB |
Output is correct |
6 |
Correct |
3 ms |
5072 KB |
Output is correct |
7 |
Correct |
4 ms |
5072 KB |
Output is correct |
8 |
Correct |
4 ms |
5200 KB |
Output is correct |
9 |
Correct |
3 ms |
5180 KB |
Output is correct |
10 |
Correct |
4 ms |
5200 KB |
Output is correct |
11 |
Correct |
4 ms |
5184 KB |
Output is correct |
12 |
Correct |
3 ms |
5072 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
4944 KB |
Output is correct |
3 |
Correct |
3 ms |
5112 KB |
Output is correct |
4 |
Correct |
3 ms |
5072 KB |
Output is correct |
5 |
Correct |
3 ms |
5072 KB |
Output is correct |
6 |
Correct |
3 ms |
5060 KB |
Output is correct |
7 |
Correct |
3 ms |
5072 KB |
Output is correct |
8 |
Correct |
4 ms |
5140 KB |
Output is correct |
9 |
Correct |
3 ms |
4944 KB |
Output is correct |
10 |
Correct |
3 ms |
5072 KB |
Output is correct |
11 |
Correct |
4 ms |
5080 KB |
Output is correct |
12 |
Correct |
3 ms |
5072 KB |
Output is correct |
13 |
Correct |
4 ms |
5072 KB |
Output is correct |
14 |
Correct |
3 ms |
5072 KB |
Output is correct |
15 |
Correct |
4 ms |
5072 KB |
Output is correct |
16 |
Correct |
4 ms |
5200 KB |
Output is correct |
17 |
Correct |
3 ms |
5180 KB |
Output is correct |
18 |
Correct |
4 ms |
5200 KB |
Output is correct |
19 |
Correct |
4 ms |
5184 KB |
Output is correct |
20 |
Correct |
3 ms |
5072 KB |
Output is correct |
21 |
Correct |
3 ms |
5176 KB |
Output is correct |
22 |
Correct |
3 ms |
5072 KB |
Output is correct |
23 |
Correct |
3 ms |
5072 KB |
Output is correct |
24 |
Correct |
4 ms |
5072 KB |
Output is correct |
25 |
Correct |
3 ms |
5196 KB |
Output is correct |
26 |
Correct |
3 ms |
5072 KB |
Output is correct |
27 |
Correct |
4 ms |
5200 KB |
Output is correct |
28 |
Correct |
4 ms |
5084 KB |
Output is correct |
29 |
Correct |
5 ms |
5072 KB |
Output is correct |
30 |
Correct |
3 ms |
5072 KB |
Output is correct |
31 |
Correct |
4 ms |
5072 KB |
Output is correct |
32 |
Correct |
3 ms |
5072 KB |
Output is correct |
33 |
Correct |
4 ms |
5072 KB |
Output is correct |
34 |
Correct |
3 ms |
5072 KB |
Output is correct |
35 |
Correct |
3 ms |
5128 KB |
Output is correct |
36 |
Correct |
4 ms |
5200 KB |
Output is correct |
37 |
Correct |
3 ms |
5324 KB |
Output is correct |
38 |
Correct |
3 ms |
5200 KB |
Output is correct |
39 |
Correct |
3 ms |
5072 KB |
Output is correct |
40 |
Correct |
3 ms |
5156 KB |
Output is correct |
41 |
Correct |
3 ms |
5072 KB |
Output is correct |
42 |
Correct |
4 ms |
5072 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
773 ms |
9616 KB |
Output is correct |
2 |
Correct |
876 ms |
14216 KB |
Output is correct |
3 |
Correct |
665 ms |
14264 KB |
Output is correct |
4 |
Correct |
840 ms |
14224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
773 ms |
9616 KB |
Output is correct |
2 |
Correct |
876 ms |
14216 KB |
Output is correct |
3 |
Correct |
665 ms |
14264 KB |
Output is correct |
4 |
Correct |
840 ms |
14224 KB |
Output is correct |
5 |
Correct |
732 ms |
9856 KB |
Output is correct |
6 |
Incorrect |
1137 ms |
14624 KB |
182nd lines differ - on the 1st token, expected: '972396080', found: '121498278' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
5072 KB |
Output is correct |
3 |
Correct |
4 ms |
5080 KB |
Output is correct |
4 |
Correct |
3 ms |
5072 KB |
Output is correct |
5 |
Correct |
4 ms |
5072 KB |
Output is correct |
6 |
Correct |
3 ms |
5072 KB |
Output is correct |
7 |
Correct |
4 ms |
5072 KB |
Output is correct |
8 |
Correct |
4 ms |
5200 KB |
Output is correct |
9 |
Correct |
3 ms |
5180 KB |
Output is correct |
10 |
Correct |
4 ms |
5200 KB |
Output is correct |
11 |
Correct |
4 ms |
5184 KB |
Output is correct |
12 |
Correct |
3 ms |
5072 KB |
Output is correct |
13 |
Correct |
773 ms |
9616 KB |
Output is correct |
14 |
Correct |
876 ms |
14216 KB |
Output is correct |
15 |
Correct |
665 ms |
14264 KB |
Output is correct |
16 |
Correct |
840 ms |
14224 KB |
Output is correct |
17 |
Correct |
732 ms |
9856 KB |
Output is correct |
18 |
Incorrect |
1137 ms |
14624 KB |
182nd lines differ - on the 1st token, expected: '972396080', found: '121498278' |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
4944 KB |
Output is correct |
3 |
Correct |
3 ms |
5112 KB |
Output is correct |
4 |
Correct |
3 ms |
5072 KB |
Output is correct |
5 |
Correct |
3 ms |
5072 KB |
Output is correct |
6 |
Correct |
3 ms |
5060 KB |
Output is correct |
7 |
Correct |
3 ms |
5072 KB |
Output is correct |
8 |
Correct |
4 ms |
5140 KB |
Output is correct |
9 |
Correct |
3 ms |
4944 KB |
Output is correct |
10 |
Correct |
3 ms |
5072 KB |
Output is correct |
11 |
Correct |
4 ms |
5080 KB |
Output is correct |
12 |
Correct |
3 ms |
5072 KB |
Output is correct |
13 |
Correct |
4 ms |
5072 KB |
Output is correct |
14 |
Correct |
3 ms |
5072 KB |
Output is correct |
15 |
Correct |
4 ms |
5072 KB |
Output is correct |
16 |
Correct |
4 ms |
5200 KB |
Output is correct |
17 |
Correct |
3 ms |
5180 KB |
Output is correct |
18 |
Correct |
4 ms |
5200 KB |
Output is correct |
19 |
Correct |
4 ms |
5184 KB |
Output is correct |
20 |
Correct |
3 ms |
5072 KB |
Output is correct |
21 |
Correct |
3 ms |
5176 KB |
Output is correct |
22 |
Correct |
3 ms |
5072 KB |
Output is correct |
23 |
Correct |
3 ms |
5072 KB |
Output is correct |
24 |
Correct |
4 ms |
5072 KB |
Output is correct |
25 |
Correct |
3 ms |
5196 KB |
Output is correct |
26 |
Correct |
3 ms |
5072 KB |
Output is correct |
27 |
Correct |
4 ms |
5200 KB |
Output is correct |
28 |
Correct |
4 ms |
5084 KB |
Output is correct |
29 |
Correct |
5 ms |
5072 KB |
Output is correct |
30 |
Correct |
3 ms |
5072 KB |
Output is correct |
31 |
Correct |
4 ms |
5072 KB |
Output is correct |
32 |
Correct |
3 ms |
5072 KB |
Output is correct |
33 |
Correct |
4 ms |
5072 KB |
Output is correct |
34 |
Correct |
3 ms |
5072 KB |
Output is correct |
35 |
Correct |
3 ms |
5128 KB |
Output is correct |
36 |
Correct |
4 ms |
5200 KB |
Output is correct |
37 |
Correct |
3 ms |
5324 KB |
Output is correct |
38 |
Correct |
3 ms |
5200 KB |
Output is correct |
39 |
Correct |
3 ms |
5072 KB |
Output is correct |
40 |
Correct |
3 ms |
5156 KB |
Output is correct |
41 |
Correct |
3 ms |
5072 KB |
Output is correct |
42 |
Correct |
4 ms |
5072 KB |
Output is correct |
43 |
Correct |
447 ms |
5456 KB |
Output is correct |
44 |
Correct |
779 ms |
5584 KB |
Output is correct |
45 |
Correct |
752 ms |
5456 KB |
Output is correct |
46 |
Correct |
1037 ms |
5840 KB |
Output is correct |
47 |
Correct |
1020 ms |
5876 KB |
Output is correct |
48 |
Correct |
933 ms |
5840 KB |
Output is correct |
49 |
Correct |
1014 ms |
5840 KB |
Output is correct |
50 |
Correct |
804 ms |
5712 KB |
Output is correct |
51 |
Correct |
927 ms |
5584 KB |
Output is correct |
52 |
Correct |
822 ms |
5712 KB |
Output is correct |
53 |
Correct |
846 ms |
5712 KB |
Output is correct |
54 |
Correct |
863 ms |
5840 KB |
Output is correct |
55 |
Correct |
916 ms |
5712 KB |
Output is correct |
56 |
Correct |
802 ms |
5712 KB |
Output is correct |
57 |
Correct |
676 ms |
5584 KB |
Output is correct |
58 |
Correct |
929 ms |
6212 KB |
Output is correct |
59 |
Correct |
1020 ms |
6444 KB |
Output is correct |
60 |
Correct |
841 ms |
6336 KB |
Output is correct |
61 |
Correct |
906 ms |
5584 KB |
Output is correct |
62 |
Correct |
828 ms |
5476 KB |
Output is correct |
63 |
Correct |
931 ms |
5456 KB |
Output is correct |
64 |
Correct |
941 ms |
5584 KB |
Output is correct |
65 |
Correct |
419 ms |
5328 KB |
Output is correct |
66 |
Correct |
956 ms |
5584 KB |
Output is correct |
67 |
Correct |
859 ms |
5584 KB |
Output is correct |
68 |
Correct |
973 ms |
5584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
3 ms |
4944 KB |
Output is correct |
3 |
Correct |
3 ms |
5112 KB |
Output is correct |
4 |
Correct |
3 ms |
5072 KB |
Output is correct |
5 |
Correct |
3 ms |
5072 KB |
Output is correct |
6 |
Correct |
3 ms |
5060 KB |
Output is correct |
7 |
Correct |
3 ms |
5072 KB |
Output is correct |
8 |
Correct |
4 ms |
5140 KB |
Output is correct |
9 |
Correct |
3 ms |
4944 KB |
Output is correct |
10 |
Correct |
3 ms |
5072 KB |
Output is correct |
11 |
Correct |
4 ms |
5080 KB |
Output is correct |
12 |
Correct |
3 ms |
5072 KB |
Output is correct |
13 |
Correct |
4 ms |
5072 KB |
Output is correct |
14 |
Correct |
3 ms |
5072 KB |
Output is correct |
15 |
Correct |
4 ms |
5072 KB |
Output is correct |
16 |
Correct |
4 ms |
5200 KB |
Output is correct |
17 |
Correct |
3 ms |
5180 KB |
Output is correct |
18 |
Correct |
4 ms |
5200 KB |
Output is correct |
19 |
Correct |
4 ms |
5184 KB |
Output is correct |
20 |
Correct |
3 ms |
5072 KB |
Output is correct |
21 |
Correct |
3 ms |
5176 KB |
Output is correct |
22 |
Correct |
3 ms |
5072 KB |
Output is correct |
23 |
Correct |
3 ms |
5072 KB |
Output is correct |
24 |
Correct |
4 ms |
5072 KB |
Output is correct |
25 |
Correct |
3 ms |
5196 KB |
Output is correct |
26 |
Correct |
3 ms |
5072 KB |
Output is correct |
27 |
Correct |
4 ms |
5200 KB |
Output is correct |
28 |
Correct |
4 ms |
5084 KB |
Output is correct |
29 |
Correct |
5 ms |
5072 KB |
Output is correct |
30 |
Correct |
3 ms |
5072 KB |
Output is correct |
31 |
Correct |
4 ms |
5072 KB |
Output is correct |
32 |
Correct |
3 ms |
5072 KB |
Output is correct |
33 |
Correct |
4 ms |
5072 KB |
Output is correct |
34 |
Correct |
3 ms |
5072 KB |
Output is correct |
35 |
Correct |
3 ms |
5128 KB |
Output is correct |
36 |
Correct |
4 ms |
5200 KB |
Output is correct |
37 |
Correct |
3 ms |
5324 KB |
Output is correct |
38 |
Correct |
3 ms |
5200 KB |
Output is correct |
39 |
Correct |
3 ms |
5072 KB |
Output is correct |
40 |
Correct |
3 ms |
5156 KB |
Output is correct |
41 |
Correct |
3 ms |
5072 KB |
Output is correct |
42 |
Correct |
4 ms |
5072 KB |
Output is correct |
43 |
Correct |
773 ms |
9616 KB |
Output is correct |
44 |
Correct |
876 ms |
14216 KB |
Output is correct |
45 |
Correct |
665 ms |
14264 KB |
Output is correct |
46 |
Correct |
840 ms |
14224 KB |
Output is correct |
47 |
Correct |
732 ms |
9856 KB |
Output is correct |
48 |
Incorrect |
1137 ms |
14624 KB |
182nd lines differ - on the 1st token, expected: '972396080', found: '121498278' |
49 |
Halted |
0 ms |
0 KB |
- |