| 10770 | 2024-04-11 17:22:58 | 111 | Gyors utak | cpp17 | Wrong answer 0/100 | 201ms | 38996 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct ST{
int n;
vector<int>t,x;
ST(int n):n(n),t(n*4),x(n*4){
}
void pull(int i,int l,int r){
t[i]=t[i*2+1]+t[i*2+2];
}
void push(int i,int l,int r){
if(x[i]){
x[i]=0;
t[i*2+1]=((l+r)/2-l+1)-t[i*2+1];
t[i*2+2]=(r-(l+r)/2)-t[i*2+2];
x[i*2+1]^=1;
x[i*2+2]^=1;
}
}
void update(int i,int l,int r,int ll,int rr){
if(l>rr||r<ll){
return;
}
if(l>=ll&&r<=rr){
t[i]=(r-l+1)-t[i];
x[i]^=1;
return;
}
push(i,l,r);
update(i*2+1,l,(l+r)/2,ll,rr);
update(i*2+2,(l+r)/2+1,r,ll,rr);
pull(i,l,r);
}
void update(int ll,int rr){
update(0,0,n-1,ll,rr);
}
int query(int i,int l,int r,int ll,int rr){
if(l>rr||r<ll){
return 0;
}
if(l>=ll&&r<=rr){
return t[i];
}
push(i,l,r);
return query(i*2+1,l,(l+r)/2,ll,rr)+query(i*2+2,(l+r)/2+1,r,ll,rr);
}
int query(int ll,int rr){
return query(0,0,n-1,ll,rr);
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef CB
freopen("be1.txt","r",stdin);
// freopen("ki.txt","w",stdout);
#endif
int N,Q;
cin>>N>>Q;
vector<vector<int>>g(N+1);
for(int i=2;i<=N;i++){
int p;
cin>>p;
g[p].push_back(i);
}
vector<int>ti(N+1),to(N+1);
int t=0;
auto dfs=[&](auto self,int i)->void{
ti[i]=t++;
for(int j:g[i]){
self(self,j);
}
to[i]=t;
};
dfs(dfs,1);
ST st(N);
for(int i=2;i<=N;i++){
int w;
cin>>w;
if(w){
st.update(ti[i],to[i]-1);
}
}
auto ans=[&]()->int{
int s=st.query(0,N-1);
return s*(s-1)/2+(N-s)*(N-s-1)/2;
};
cout<<ans()<<'\n';
while(Q--){
int i;
cin>>i;
i++;
st.update(ti[i],to[i]-1);
cout<<ans()<<'\n';
}
return 0;
}
| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Wrong answer | 3ms | 1824 KiB | ||||
| 2 | Wrong answer | 4ms | 3008 KiB | ||||
| subtask2 | 0/10 | ||||||
| 3 | Wrong answer | 3ms | 2296 KiB | ||||
| 4 | Wrong answer | 3ms | 2360 KiB | ||||
| 5 | Wrong answer | 3ms | 2688 KiB | ||||
| 6 | Wrong answer | 3ms | 2744 KiB | ||||
| 7 | Wrong answer | 3ms | 2760 KiB | ||||
| 8 | Wrong answer | 3ms | 2920 KiB | ||||
| subtask3 | 0/11 | ||||||
| 9 | Wrong answer | 3ms | 2296 KiB | ||||
| 10 | Wrong answer | 3ms | 2360 KiB | ||||
| 11 | Wrong answer | 3ms | 2688 KiB | ||||
| 12 | Wrong answer | 3ms | 2744 KiB | ||||
| 13 | Wrong answer | 3ms | 2760 KiB | ||||
| 14 | Wrong answer | 3ms | 2920 KiB | ||||
| 15 | Wrong answer | 6ms | 3636 KiB | ||||
| 16 | Wrong answer | 6ms | 3540 KiB | ||||
| 17 | Wrong answer | 6ms | 3448 KiB | ||||
| 18 | Wrong answer | 4ms | 3428 KiB | ||||
| 19 | Wrong answer | 6ms | 3708 KiB | ||||
| 20 | Wrong answer | 4ms | 3636 KiB | ||||
| 21 | Wrong answer | 6ms | 3800 KiB | ||||
| 22 | Wrong answer | 6ms | 3796 KiB | ||||
| 23 | Wrong answer | 6ms | 4076 KiB | ||||
| 24 | Wrong answer | 6ms | 4340 KiB | ||||
| subtask4 | 0/21 | ||||||
| 25 | Wrong answer | 172ms | 38800 KiB | ||||
| 26 | Wrong answer | 175ms | 38796 KiB | ||||
| 27 | Wrong answer | 188ms | 38720 KiB | ||||
| 28 | Wrong answer | 160ms | 38752 KiB | ||||
| 29 | Wrong answer | 181ms | 38996 KiB | ||||
| 30 | Wrong answer | 184ms | 38988 KiB | ||||
| subtask5 | 0/24 | ||||||
| 31 | Wrong answer | 3ms | 4276 KiB | ||||
| 32 | Wrong answer | 12ms | 6472 KiB | ||||
| 33 | Wrong answer | 93ms | 27600 KiB | ||||
| 34 | Wrong answer | 174ms | 27600 KiB | ||||
| subtask6 | 0/34 | ||||||
| 35 | Wrong answer | 3ms | 2296 KiB | ||||
| 36 | Wrong answer | 3ms | 2360 KiB | ||||
| 37 | Wrong answer | 3ms | 2688 KiB | ||||
| 38 | Wrong answer | 3ms | 2744 KiB | ||||
| 39 | Wrong answer | 3ms | 2760 KiB | ||||
| 40 | Wrong answer | 3ms | 2920 KiB | ||||
| 41 | Wrong answer | 6ms | 3636 KiB | ||||
| 42 | Wrong answer | 6ms | 3540 KiB | ||||
| 43 | Wrong answer | 6ms | 3448 KiB | ||||
| 44 | Wrong answer | 4ms | 3428 KiB | ||||
| 45 | Wrong answer | 6ms | 3708 KiB | ||||
| 46 | Wrong answer | 4ms | 3636 KiB | ||||
| 47 | Wrong answer | 6ms | 3800 KiB | ||||
| 48 | Wrong answer | 6ms | 3796 KiB | ||||
| 49 | Wrong answer | 6ms | 4076 KiB | ||||
| 50 | Wrong answer | 6ms | 4340 KiB | ||||
| 51 | Wrong answer | 172ms | 38800 KiB | ||||
| 52 | Wrong answer | 175ms | 38796 KiB | ||||
| 53 | Wrong answer | 188ms | 38720 KiB | ||||
| 54 | Wrong answer | 160ms | 38752 KiB | ||||
| 55 | Wrong answer | 181ms | 38996 KiB | ||||
| 56 | Wrong answer | 184ms | 38988 KiB | ||||
| 57 | Wrong answer | 3ms | 4276 KiB | ||||
| 58 | Wrong answer | 12ms | 6472 KiB | ||||
| 59 | Wrong answer | 93ms | 27600 KiB | ||||
| 60 | Wrong answer | 174ms | 27600 KiB | ||||
| 61 | Wrong answer | 179ms | 28136 KiB | ||||
| 62 | Wrong answer | 165ms | 27184 KiB | ||||
| 63 | Wrong answer | 168ms | 27556 KiB | ||||
| 64 | Wrong answer | 168ms | 27192 KiB | ||||
| 65 | Wrong answer | 184ms | 28628 KiB | ||||
| 66 | Wrong answer | 187ms | 28596 KiB | ||||
| 67 | Wrong answer | 182ms | 28740 KiB | ||||
| 68 | Wrong answer | 193ms | 28684 KiB | ||||
| 69 | Wrong answer | 150ms | 26340 KiB | ||||
| 70 | Wrong answer | 193ms | 28700 KiB | ||||
| 71 | Wrong answer | 148ms | 26168 KiB | ||||
| 72 | Wrong answer | 186ms | 29136 KiB | ||||
| 73 | Wrong answer | 189ms | 29452 KiB | ||||
| 74 | Wrong answer | 122ms | 29316 KiB | ||||
| 75 | Wrong answer | 201ms | 28628 KiB | ||||
| 76 | Wrong answer | 184ms | 28772 KiB | ||||
| 77 | Wrong answer | 162ms | 27012 KiB | ||||