Submission #1078536

#TimeUsernameProblemLanguageResultExecution timeMemory
1078536ArthuroWichDigital Circuit (IOI22_circuit)C++17
100 / 100
813 ms41456 KiB
#include "circuit.h" #include<bits/stdc++.h> using namespace std; #define int long long int vector<int> adj[200005]; int v[200005], a[200005], arr[200005], brr[200005], seg1[4*200005], seg0[4*200005], s[4*200005], dep[200005], mod = 1000002022; void lazypropagate(int n, int l, int r) { if (s[n]) { swap(seg1[n], seg0[n]); if (l != r) { s[2*n] ^= 1; s[2*n+1] ^= 1; } s[n] = 0; } } void build(int n, int l, int r) { if (l == r) { seg1[n] = arr[l]; seg0[n] = brr[l]; } else { int m = (l+r)/2; build(2*n, l, m); build(2*n+1, m+1, r); seg1[n] = seg1[2*n] + seg1[2*n+1]; seg1[n] %= mod; seg0[n] = seg0[2*n] + seg0[2*n+1]; seg0[n] %= mod; } } void update(int n, int l, int r, int a, int b) { lazypropagate(n, l, r); if (b < l || r < a) { return; } else if (a <= l && r <= b) { s[n] = 1; lazypropagate(n, l, r); } else { int m = (l+r)/2; update(2*n, l, m, a, b); update(2*n+1, m+1, r, a, b); seg1[n] = seg1[2*n] + seg1[2*n+1]; seg1[n] %= mod; seg0[n] = seg0[2*n] + seg0[2*n+1]; seg0[n] %= mod; } } int n, m; void dfs1(int i) { if (adj[i].size() == 0) { v[i] = 1; } else { v[i] = adj[i].size(); } for (int j : adj[i]) { dfs1(j); } for (int j : adj[i]) { v[i] *= v[j]; v[i] %= mod; } } void dfs2(int i, int va) { if (adj[i].size() == 0) { a[i] = va; return; } int l = adj[i].size(); vector<int> pref(l+2, 1), suff(l+2, 1); for (int j = 1; j <= l; j++) { pref[j] = v[adj[i][j-1]]; suff[j] = v[adj[i][j-1]]; } for (int j = 1; j <= l+1; j++) { pref[j] *= pref[j-1]; pref[j] %= mod; } for (int j = l; j >= 0; j--) { suff[j] *= suff[j+1]; suff[j] %= mod; } for (int j = 1; j <= l; j++) { int b = pref[j-1]*suff[j+1]; b %= mod; b *= va; b %= mod; dfs2(adj[i][j-1], b); } } void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) { n = N, m = M; for (int i = 1; i <= n+m-1; i++) { adj[P[i]].push_back(i); } vector<int> b(n+1, 1); for (int i = 1; i <= n; i++) { b[i] = b[i-1]*2; b[i] %= mod; } dfs1(0); dfs2(0, 1); for (int i = 0; i < m; i++) { if (A[i]) { arr[i] = a[i+n]; } else { brr[i] = a[i+n]; } } build(1, 0, m-1); } int32_t count_ways(int32_t L, int32_t R) { update(1, 0, m-1, L-n, R-n); return seg1[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...