#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];
int 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);
for (int i:g[cur]){
dfs1(i);
sz[cur]*=sz[i];
sz[cur]%=mod;
}
if (!g[cur].size()){
return;
} else {
int 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]];
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]];
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;
}
}
}
void dfs2(int cur){
for (int i:g[cur]){
ac[i]=ac[cur]*d[i]%mod;
dfs2(i);
}
}
void build(int id,int tl,int tr){
if (tl==tr){
seg[id]=a[tl]*weight[tl];
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,r),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];
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);
}
Compilation message
circuit.cpp: In function 'void dfs1(int)':
circuit.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i=0; i<g[cur].size(); i++){
| ~^~~~~~~~~~~~~~
circuit.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | if (i==g[cur].size()-1) ba[i]=sz[g[cur][i]];
| ~^~~~~~~~~~~~~~~~~
circuit.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i=0; i<g[cur].size(); i++){
| ~^~~~~~~~~~~~~~
circuit.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if (i+1<g[cur].size()) t=t*ba[i+1]%mod;
| ~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5200 KB |
1st lines differ - on the 1st token, expected: '509', found: '498' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5072 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '629849836' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5200 KB |
1st lines differ - on the 1st token, expected: '509', found: '498' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
599 ms |
9620 KB |
Output is correct |
| 2 |
Correct |
843 ms |
14204 KB |
Output is correct |
| 3 |
Correct |
833 ms |
14208 KB |
Output is correct |
| 4 |
Correct |
766 ms |
14248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
599 ms |
9620 KB |
Output is correct |
| 2 |
Correct |
843 ms |
14204 KB |
Output is correct |
| 3 |
Correct |
833 ms |
14208 KB |
Output is correct |
| 4 |
Correct |
766 ms |
14248 KB |
Output is correct |
| 5 |
Incorrect |
719 ms |
9832 KB |
1st lines differ - on the 1st token, expected: '105182172', found: '40177750' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5072 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '629849836' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5200 KB |
1st lines differ - on the 1st token, expected: '509', found: '498' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5200 KB |
1st lines differ - on the 1st token, expected: '509', found: '498' |
| 4 |
Halted |
0 ms |
0 KB |
- |
