10770 | 2024-04-11 17:22:58 | 111 | Gyors utak | cpp17 | Hibás válasz 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;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Hibás válasz | 3ms | 1824 KiB | ||||
2 | Hibás válasz | 4ms | 3008 KiB | ||||
subtask2 | 0/10 | ||||||
3 | Hibás válasz | 3ms | 2296 KiB | ||||
4 | Hibás válasz | 3ms | 2360 KiB | ||||
5 | Hibás válasz | 3ms | 2688 KiB | ||||
6 | Hibás válasz | 3ms | 2744 KiB | ||||
7 | Hibás válasz | 3ms | 2760 KiB | ||||
8 | Hibás válasz | 3ms | 2920 KiB | ||||
subtask3 | 0/11 | ||||||
9 | Hibás válasz | 3ms | 2296 KiB | ||||
10 | Hibás válasz | 3ms | 2360 KiB | ||||
11 | Hibás válasz | 3ms | 2688 KiB | ||||
12 | Hibás válasz | 3ms | 2744 KiB | ||||
13 | Hibás válasz | 3ms | 2760 KiB | ||||
14 | Hibás válasz | 3ms | 2920 KiB | ||||
15 | Hibás válasz | 6ms | 3636 KiB | ||||
16 | Hibás válasz | 6ms | 3540 KiB | ||||
17 | Hibás válasz | 6ms | 3448 KiB | ||||
18 | Hibás válasz | 4ms | 3428 KiB | ||||
19 | Hibás válasz | 6ms | 3708 KiB | ||||
20 | Hibás válasz | 4ms | 3636 KiB | ||||
21 | Hibás válasz | 6ms | 3800 KiB | ||||
22 | Hibás válasz | 6ms | 3796 KiB | ||||
23 | Hibás válasz | 6ms | 4076 KiB | ||||
24 | Hibás válasz | 6ms | 4340 KiB | ||||
subtask4 | 0/21 | ||||||
25 | Hibás válasz | 172ms | 38800 KiB | ||||
26 | Hibás válasz | 175ms | 38796 KiB | ||||
27 | Hibás válasz | 188ms | 38720 KiB | ||||
28 | Hibás válasz | 160ms | 38752 KiB | ||||
29 | Hibás válasz | 181ms | 38996 KiB | ||||
30 | Hibás válasz | 184ms | 38988 KiB | ||||
subtask5 | 0/24 | ||||||
31 | Hibás válasz | 3ms | 4276 KiB | ||||
32 | Hibás válasz | 12ms | 6472 KiB | ||||
33 | Hibás válasz | 93ms | 27600 KiB | ||||
34 | Hibás válasz | 174ms | 27600 KiB | ||||
subtask6 | 0/34 | ||||||
35 | Hibás válasz | 3ms | 2296 KiB | ||||
36 | Hibás válasz | 3ms | 2360 KiB | ||||
37 | Hibás válasz | 3ms | 2688 KiB | ||||
38 | Hibás válasz | 3ms | 2744 KiB | ||||
39 | Hibás válasz | 3ms | 2760 KiB | ||||
40 | Hibás válasz | 3ms | 2920 KiB | ||||
41 | Hibás válasz | 6ms | 3636 KiB | ||||
42 | Hibás válasz | 6ms | 3540 KiB | ||||
43 | Hibás válasz | 6ms | 3448 KiB | ||||
44 | Hibás válasz | 4ms | 3428 KiB | ||||
45 | Hibás válasz | 6ms | 3708 KiB | ||||
46 | Hibás válasz | 4ms | 3636 KiB | ||||
47 | Hibás válasz | 6ms | 3800 KiB | ||||
48 | Hibás válasz | 6ms | 3796 KiB | ||||
49 | Hibás válasz | 6ms | 4076 KiB | ||||
50 | Hibás válasz | 6ms | 4340 KiB | ||||
51 | Hibás válasz | 172ms | 38800 KiB | ||||
52 | Hibás válasz | 175ms | 38796 KiB | ||||
53 | Hibás válasz | 188ms | 38720 KiB | ||||
54 | Hibás válasz | 160ms | 38752 KiB | ||||
55 | Hibás válasz | 181ms | 38996 KiB | ||||
56 | Hibás válasz | 184ms | 38988 KiB | ||||
57 | Hibás válasz | 3ms | 4276 KiB | ||||
58 | Hibás válasz | 12ms | 6472 KiB | ||||
59 | Hibás válasz | 93ms | 27600 KiB | ||||
60 | Hibás válasz | 174ms | 27600 KiB | ||||
61 | Hibás válasz | 179ms | 28136 KiB | ||||
62 | Hibás válasz | 165ms | 27184 KiB | ||||
63 | Hibás válasz | 168ms | 27556 KiB | ||||
64 | Hibás válasz | 168ms | 27192 KiB | ||||
65 | Hibás válasz | 184ms | 28628 KiB | ||||
66 | Hibás válasz | 187ms | 28596 KiB | ||||
67 | Hibás válasz | 182ms | 28740 KiB | ||||
68 | Hibás válasz | 193ms | 28684 KiB | ||||
69 | Hibás válasz | 150ms | 26340 KiB | ||||
70 | Hibás válasz | 193ms | 28700 KiB | ||||
71 | Hibás válasz | 148ms | 26168 KiB | ||||
72 | Hibás válasz | 186ms | 29136 KiB | ||||
73 | Hibás válasz | 189ms | 29452 KiB | ||||
74 | Hibás válasz | 122ms | 29316 KiB | ||||
75 | Hibás válasz | 201ms | 28628 KiB | ||||
76 | Hibás válasz | 184ms | 28772 KiB | ||||
77 | Hibás válasz | 162ms | 27012 KiB |