Submission #966445

#TimeUsernameProblemLanguageResultExecution timeMemory
966445ZeroCoolDigital Circuit (IOI22_circuit)C++17
2 / 100
414 ms15144 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() using ll = long long; const int N = 3e5 + 10; const int MOD = 1000002022; int n, m; int A[N]; vector<int> g[N]; int sz[N]; void dfs1(int x){ sz[x] = g[x].size(); for(auto u: g[x]){ dfs1(u); sz[x] *= sz[u]; sz[x] %= MOD; } if(!sz[x])sz[x] = 1; } int X[N]; void dfs2(int x,int w){ X[x] = w; int k = g[x].size(); int pref[k], suff[k]; for(int i = 0;i<k;i++){ pref[i] = sz[g[x][i]]; if(i) pref[i] = (pref[i-1] * pref[i]) % MOD; } for(int i = k - 1;i>=0;i--){ suff[i] = sz[g[x][i]]; if(i +1 < k)suff[i] = (suff[i] * suff[i+1]) % MOD; } for(int i = 0;i<k;i++){ int prod = w; if(i)prod = (prod * pref[i-1]) % MOD; if(i + 1 < k)prod = (prod * suff[i+1]) % MOD; dfs2(g[x][i], prod); } } array<ll, 2> t[4 * N]; bool lazy[4 * N]; void build(int k,int tl,int tr){ if(tl == tr){ t[k] = {X[tl], 0}; if(A[tl])swap(t[k][0], t[k][1]); return; } int tm = (tl + tr) / 2; build(k *2, tl, tm); build(k*2+1, tm + 1, tr); t[k][0] = (t[k*2][0] + t[k*2+1][0]) % MOD; t[k][1] = (t[k*2][1] + t[k*2+1][1]) % MOD; } void push(int k){ if(!lazy[k])return; lazy[k*2] ^= 1; lazy[k*2+1] ^= 1; swap(t[k*2][0], t[k*2][1]); swap(t[k*2+1][0], t[k*2+1][1]); lazy[k] = 0; } void update(int k,int tl,int tr,int l,int r){ if(r < tl || tr < l)return; if(l <= tl && tr <= r){ lazy[k] ^= 1; swap(t[k][0], t[k][1]); return; } push(k); int tm = (tl + tr) / 2; update(k * 2, tl, tm, l, r); update(k*2+1, tm+1,tr, l, r); t[k][0] = (t[k*2][0] + t[k*2+1][0]) % MOD; t[k][1] = (t[k*2][1] + t[k*2+1][1]) % MOD; } void init(int nn, int mm, std::vector<int> P, std::vector<int> a) { n = nn; m = mm; for(int i = 1;i < n + m;i++){ g[P[i]].pb(i); } for(int i = n;i<n + m;i++)A[i] = a[i - n]; dfs1(0); dfs2(0, 1); build(1, n, n + m - 1); } int count_ways(int L, int R) { update(1, n, n + m - 1, L, R); return t[1][1]; }
#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...