| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1216497 | user736482 | Digital Circuit (IOI22_circuit) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000002022
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll n,m;
ll par[200007],vl[200007],ost[200007];
vector<ll>d[200007];
ll sm;
ll sgtree[POT];
bool inv[POT];
void spych(ll v){
if(!inv[v])return;
inv[v*2]^=1;
inv[v*2+1]^=1;
sgtree[v*2]*=-1;
sgtree[v*2+1]*=-1;
inv[v]=1;
}
void ch(ll v,ll l,ll r,ll pocz,ll kon){
if(l>kon || r<pocz)return;
if(l>=pocz && r<=kon){sgtree[v]*=-1;inv[v]^=1;}
else{spych(v);ch(v*2,l,(l+r)/2,pocz,kon);ch(v*2+1,(l+r)/2+1,r,pocz,kon);sgtree[v]=sgtree[v*2]+sgtree[v*2+1];}
}
void init(int N,int M,vector<int>p,vector<int>a){
n=N+M;
m=M;
for(ll i=1;i<n;i++){
par[i]=p[i];
d[p[i]].pb(i);
}
for(ll i=0;i<n;i++){
vl[i]=max(1,(int)d[i].size());
}
for(ll i=n-1;i>=0;i--){
for(ll j : d[i])vl[i]=(vl[i]*vl[j])%MOD;
}
ost[0]=1;
for(ll i=0;i<n-m;i++){
vector<ll>v1={1},v2={1};
for(ll j=0;j<d[i].size();j++)v1.pb((v1.back()*vl[d[i][j]])%MOD);
for(ll j=d[i].size()-1;j>=0;j--)v2.pb((v2.back()*vl[d[i][j]])%MOD);
for(ll j=0;j<d[i].size();j++){
ost[d[i][j]]=(ost[i]*v1[j])%MOD*v2[d[i].size()-j-1];ost[d[i][j]]%=MOD;
}
}
for(ll i=n-m;i<n;i++)sgtree[i+POT/2-n+m]=-ost[i];
for(ll i=POT/2-1;i>0;i--)sgtree[i]=sgtree[i*2]+sgtree[i*2+1];
for(ll i=n-m;i<n;i++){sm+=ost[i];if(a[i-n+m])ch(1,1,POT/2,i-n+m+1,i-n+m+1);}
}