Submission #627422

#TimeUsernameProblemLanguageResultExecution timeMemory
627422KaitokidDigital Circuit (IOI22_circuit)C++17
2 / 100
639 ms7828 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; int mod=1000002022; vector<int>ch[200009]; int sz[200009], f[200009],n,m; void dfs(int x) { if(ch[x].empty()){sz[x]=1;return;} sz[x]=ch[x].size(); for(int i=0;i<ch[x].size();i++){dfs(ch[x][i]);sz[x]=(sz[x]*1LL*sz[ch[x][i]])%mod;} } int suf[200009]; void go(int x,int prd) { if(ch[x].empty()){f[x-n]=prd;return;} int w=ch[x].size(); suf[w]=1; for(int i=w-1;i>=0;i--)suf[i]=(suf[i+1]*1LL*sz[ch[x][i]])%mod; int d=1; for(int i=0;i<w;i++) { int r=(d*1LL*suf[i+1])%mod; go(ch[x][i],r); d=(d*1LL*sz[ch[x][i]])%mod; } } int sg[40009][2]; int lz[400009]; vector<int>onn; void build(int x=1,int st=0,int en=m-1) { if(st==en){sg[x][0]=f[st];sg[x][1]=f[st]*onn[st];return;} int mid=(st+en)>>1; build((x<<1),st,mid); build((x<<1)|1,mid+1,en); sg[x][0]=(sg[(x<<1)][0]+sg[(x<<1)|1][0])%mod; sg[x][1]=(sg[(x<<1)][1]+sg[(x<<1)|1][1])%mod; } void psh(int x,int st,int en) { if(lz[x]==0)return; sg[x][1]=(sg[x][0]-sg[x][1]+mod)%mod; lz[x]=0; if(en>st) { lz[(x<<1)]=1-lz[(x<<1)]; lz[(x<<1)|1]=1-lz[(x<<1)|1]; } } void upd(int l,int r,int x=1,int st=0,int en=m-1) { psh(x,st,en); if(l>en||st>r)return; if(st>=l && en<=r){lz[x]=1;psh(x,st,en);return ;} int mid=(st+en)>>1; upd(l,r,(x<<1),st,mid); upd(l,r,(x<<1)|1,mid+1,en); sg[x][0]=(sg[(x<<1)][0]+sg[(x<<1)|1][0])%mod; sg[x][1]=(sg[(x<<1)][1]+sg[(x<<1)|1][1])%mod; } void init(int N,int M,vector<int> P,vector<int> A) { n=N; m=M; onn=A; for(int i=1;i<n+m;i++) ch[P[i]].push_back(i); dfs(0); go(0,1); build(); /*for(int i=0;i<m;i++)cout<<f[i]<<" "; cout<<endl; cout<<sg[1][0]<<" "<<sg[1][1]<<endl;*/ } int count_ways(int L,int R) { upd(L-n,R-n); return sg[1][1]; }

Compilation message (stderr)

circuit.cpp: In function 'void dfs(int)':
circuit.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i=0;i<ch[x].size();i++){dfs(ch[x][i]);sz[x]=(sz[x]*1LL*sz[ch[x][i]])%mod;}
      |                 ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...