Submission #1225913

#TimeUsernameProblemLanguageResultExecution timeMemory
1225913hengliaoDigital Circuit (IOI22_circuit)C++20
100 / 100
351 ms45708 KiB
#include "circuit.h" #include<bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back #define vll vector<ll> #define pll pair<ll, ll> typedef long long ll; namespace{ const ll mxN=2e5+5; const ll mod=1000002022; ll n, m; vll adj[mxN]; vll a; ll dp[mxN]; vll pre[mxN]; vll suf[mxN]; vll c; struct segtree{ vll val, tree, lazy; ll treelen; void init(ll siz){ treelen=siz+1; while(__builtin_popcount(treelen)!=1){ treelen++; } val=vll(2*treelen); tree=vll(2*treelen); lazy=vll(2*treelen); } void build(ll idx, ll low, ll high){ if(low==high){ if(low<m){ val[idx]=c[low]; tree[idx]=a[low]*c[low]; } return; } ll mid=(low+high)/2; build(2*idx, low, mid); build(2*idx+1, mid+1, high); val[idx]=val[2*idx]+val[2*idx+1]; val[idx]%=mod; tree[idx]=tree[2*idx]+tree[2*idx+1]; tree[idx]%=mod; } void push(ll idx, ll low, ll high){ if(lazy[idx]){ tree[2*idx]=val[2*idx]-tree[2*idx]; tree[2*idx]%=mod; if(tree[2*idx]<0) tree[2*idx]+=mod; lazy[2*idx]^=1; tree[2*idx+1]=val[2*idx+1]-tree[2*idx+1]; tree[2*idx+1]%=mod; if(tree[2*idx+1]<0) tree[2*idx+1]+=mod; lazy[2*idx+1]^=1; lazy[idx]=0; } } void update1(ll idx, ll low, ll high, ll qlow, ll qhigh){ if(low>=qlow && high<=qhigh){ tree[idx]=val[idx]-tree[idx]; tree[idx]%=mod; if(tree[idx]<0) tree[idx]+=mod; lazy[idx]^=1; return; } if(low>qhigh || high<qlow){ return; } ll mid=(low+high)/2; push(idx, low, high); update1(2*idx, low, mid, qlow, qhigh); update1(2*idx+1, mid+1, high, qlow, qhigh); tree[idx]=tree[2*idx]+tree[2*idx+1]; tree[idx]%=mod; } void update(ll qlow, ll qhigh){ update1(1, 0, treelen-1, qlow, qhigh); } ll total(){ return tree[1]; } }; segtree seg; void dfs(ll cur){ if(cur>=n){ dp[cur]=1; return; } dp[cur]=(ll) adj[cur].size(); for(auto &chd:adj[cur]){ dfs(chd); dp[cur]*=dp[chd]; dp[cur]%=mod; } ll p=1; pre[cur]=vll((ll) adj[cur].size()); for(ll i=0;i<(ll) adj[cur].size();i++){ p*=dp[adj[cur][i]]; p%=mod; pre[cur][i]=p; } suf[cur]=vll((ll) adj[cur].size()); p=1; for(ll i=(ll) adj[cur].size()-1;i>=0;i--){ p*=dp[adj[cur][i]]; p%=mod; suf[cur][i]=p; } } void dfs2(ll cur, ll val){ if(cur>=n){ c[cur-n]=val; return; } for(ll i=0;i<(ll) adj[cur].size();i++){ ll new_val=val; if(i>0){ new_val*=pre[cur][i-1]; new_val%=mod; } if(i<(ll) adj[cur].size()-1){ new_val*=suf[cur][i+1]; new_val%=mod; } dfs2(adj[cur][i], new_val); } } } void init(int N, int M, vector<int> P, vector<int> A) { n=N; m=M; c=vll(m); a=vll(m); for(ll i=1;i<n+m;i++){ adj[P[i]].pb(i); } for(ll i=0;i<m;i++){ a[i]=A[i]; } dfs(0); dfs2(0, 1); seg.init(m+1); seg.build(1, 0, seg.treelen-1); } int count_ways(int L, int R) { L-=n; R-=n; seg.update(L, R); return (int) seg.total(); }
#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...