제출 #1196130

#제출 시각아이디문제언어결과실행 시간메모리
1196130hyakupDigital Circuit (IOI22_circuit)C++20
2 / 100
222 ms41648 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; using ll = long long; int n, m; const int maxn = 2e5 + 10; const int mod = 1000002022; vector<int> adj[maxn]; vector<ll> pref[maxn], suf[maxn], fator(maxn); ll dfs_init( int cur ){ pref[cur].push_back(1); suf[cur].push_back(1); ll resp = max( (int)adj[cur].size(), 1 ); for( int viz : adj[cur] ){ ll tot = dfs_init( viz ); resp *= tot; pref[cur].push_back(tot); suf[cur].push_back(tot); } pref[cur].push_back(1); suf[cur].push_back(1); for( int i = 1; i < (int)pref[cur].size(); i++ ) pref[cur][i] = (pref[cur][i - 1]*pref[cur][i])%mod; for( int i = (int)suf[cur].size() - 2; i >= 0; i-- ) suf[cur][i] = (suf[cur][i + 1]*suf[cur][i])%mod; return resp; } void dfs( int cur ){ for( int i = 0; i < (int)adj[cur].size(); i++ ){ int viz = adj[cur][i]; fator[viz] = (((fator[cur]*pref[cur][i])%mod)*suf[cur][i + 2])%mod; dfs( viz ); } } struct Node{ ll v1 = 0, v2 = 0; bool lazy = false; Node( ll v1 = 0, ll v2 = 0 ) : v1(v1), v2(v2) {} Node operator + ( Node n ){ return Node( (v1 + n.v1)%mod, (v2 + n.v2)%mod ); } } seg[4*maxn]; void build( int pos, int ini, int fim, vector<int> &a ){ if( ini == fim ){ seg[pos] = Node(fator[ini]*a[ini - n], fator[ini]*(1 - a[ini - n]) ); return; } int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2; build( l, ini, mid, a ); build( r, mid + 1, fim, a ); seg[pos] = seg[l] + seg[r]; } void refresh( int pos, int ini, int fim ){ if( !seg[pos].lazy ) return; seg[pos].lazy = false; swap( seg[pos].v1, seg[pos].v2 ); if( ini == fim ) return; int l = 2*pos, r = 2*pos + 1; seg[l].lazy ^= true; seg[r].lazy ^= true; } void update( int pos, int ini, int fim, int ki, int kf ){ refresh( pos, ini, fim ); if( ki > fim || ini > kf ) return; if( ki <= ini && fim <= kf ){ seg[pos].lazy = true; refresh( pos, ini, fim ); return; } int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2; update( l, ini, mid, ki, kf ); update( r, mid + 1, fim, ki, kf ); seg[pos] = seg[l] + seg[r]; } void init( int N, int M, vector<int> P, vector<int> A ){ n = N; m = M; for( int i = 1; i < n + m; i++ ) adj[P[i]].push_back(i); dfs_init(0); fator[0] = 1; dfs(0); build( 1, n, n + m - 1, A ); } int count_ways(int l, int r) { update( 1, n, n + m - 1, l, r ); return seg[1].v1; }
#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...