Submission #1167509

#TimeUsernameProblemLanguageResultExecution timeMemory
1167509SmuggingSpunDigital Circuit (IOI22_circuit)C++20
100 / 100
344 ms31200 KiB
#include "circuit.h" #include<bits/stdc++.h> using namespace std; const int lim = 2e5 + 5; const int mod = 1000002022; void add(int& a, int b){ if((a += b) >= mod){ a -= mod; } } void sub(int& a, int b){ if((a -= b) < 0){ a += mod; } } int n, m, parent[lim], a[lim]; vector<int>g[lim]; namespace sub1237{ const int lim = 1e4 + 5; int ans = 0, f[lim], coef[lim]; bitset<lim>vis; void init(){ for(int i = n; i < n + m; i++){ vector<int>path; int u = i; vis.reset(); while(u != -1){ vis.set(u); u = parent[u]; } f[i] = 1; for(int j = 0; j < n; j++){ if(!vis.test(j)){ f[i] = 1LL * f[i] * g[j].size() % mod; } } if(a[i] == 1){ add(ans, f[i]); } } } int query(int L, int R){ for(int i = L; i <= R; i++){ if((a[i] ^= 1) == 0){ sub(ans, f[i]); } else{ add(ans, f[i]); } } return ans; } } namespace sub8{ int f[lim], st[lim << 2]; bitset<lim << 2>lazy; void fix(int id){ st[id] = (st[id << 1] + st[id << 1 | 1]) % mod; } void flip(int id, int l, int r){ lazy.flip(id); st[id] = ((f[r] - f[l - 1] + mod) % mod - st[id] + mod) % mod; } void build(int id, int l, int r){ if(l == r){ st[id] = (a[l] == 0 ? 0 : (f[l] - f[l - 1] + mod) % mod); return; } int m = (l + r) >> 1; build(id << 1, l, m); build(id << 1 | 1, m + 1, r); fix(id); } void push_down(int id, int l, int r, int m){ if(lazy.test(id)){ lazy.reset(id); flip(id << 1, l, m); flip(id << 1 | 1, m + 1, r); } } void update(int id, int l, int r, int u, int v){ if(l > v || r < u){ return; } if(u <= l && v >= r){ flip(id, l, r); return; } int m = (l + r) >> 1; push_down(id, l, r, m); update(id << 1, l, m, u, v); update(id << 1 | 1, m + 1, r, u, v); fix(id); } void init(){ function<void(int)>dfs_1, dfs_2, dfs_3; dfs_1 = [&] (int s){ f[s] = g[s].size(); for(int& d : g[s]){ if(!g[d].empty()){ dfs_1(d); f[s] = 1LL * f[s] * f[d] % mod; } else{ f[d] = 1; } } }; dfs_1(0); dfs_2 = [&] (int s){ vector<int>suffix(g[s].size() + 2); suffix[g[s].size() + 1] = 1; for(int i = g[s].size(); i > 0; i--){ int d = g[s][i - 1]; suffix[i] = 1LL * suffix[i + 1] * f[d] % mod; } for(int i = 1, prefix = 1; i <= g[s].size(); i++){ int d = g[s][i - 1], temp = f[d]; f[d] = 1LL * prefix * suffix[i + 1] % mod; dfs_2(d); prefix = 1LL * prefix * temp % mod; } }; dfs_2(0); f[0] = 1; dfs_3 = [&] (int s){ for(int& d : g[s]){ f[d] = 1LL * f[d] * f[s] % mod; dfs_3(d); } }; dfs_3(0); f[n - 1] = 0; for(int i = n; i < n + m; i++){ add(f[i], f[i - 1]); } lazy.reset(); build(1, n, n + m - 1); } int query(int L, int R){ update(1, n, n + m - 1, L, R); return st[1]; } } void init(int N, int M, vector<int>P, vector<int>A){ n = N; m = M; parent[0] = -1; for(int i = 1; i < n + m; i++){ g[parent[i] = P[i]].emplace_back(i); } for(int i = 0; i < m; i++){ a[i + n] = A[i]; } if(max(n, m) <= 5000 && false){ sub1237::init(); } else{ sub8::init(); } } int count_ways(int L, int R){ if(max(n, m) <= 5000 && false){ return sub1237::query(L, R); } return sub8::query(L, R); }
#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...