Submission #633073

#TimeUsernameProblemLanguageResultExecution timeMemory
633073tutisDigital Circuit (IOI22_circuit)C++17
100 / 100
1150 ms40980 KiB
#include "circuit.h" #pragma GCC optimize ("O3") #include <bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 1000002022; vector<pair<ll, ll>>a; vector<int>P; vector<int>A; vector<vector<int>>c; int N, M; vector<bool> F(200009, false); vector<int> L, R; void calc(int i) { int d = c[i].size(); vector<ll> k(d + 2, 0ll); ll v = 1; a[i] = {0ll, 0ll}; for (int j : c[i]) { int v0 = a[j].first; int v1 = a[j].second; if (F[j]) swap(v0, v1); ll a1_ = 0; ll a0_ = 0; a1_ = a[i].second * (v0 + v1) + v * v1; a0_ = a[i].first * (v0 + v1) + v * v0; a[i].first = a0_; a[i].second = a1_; v *= (v0 + v1); a[i].first %= mod; a[i].second %= mod; v %= mod; } } vector<int>D; struct st { int s0, s1; int l, r; bool lazy = false; st *left; st *right; st() {} st(int l, int r): l(l), r(r) { if (l < r) { left = new st(l, (l + r) / 2); right = new st((l + r) / 2 + 1, r); s0 = left->s0 + right->s0; s1 = left->s1 + right->s1; if (s0 >= mod) s0 -= mod; if (s1 >= mod) s1 -= mod; } else { if (A[l] == 1) { s1 = D[l + N]; s0 = 0; } else { s1 = 0; s0 = D[l + N]; } } } void fix() { if (lazy) { swap(s0, s1); if (l < r) { left->lazy ^= true; right->lazy ^= true; } } lazy = false; } void fl(int x, int y) { if (x <= l && r <= y) { lazy ^= true; return fix(); } if (r < x || y < l) return fix(); fix(); left->fl(x, y); right->fl(x, y); s0 = left->s0 + right->s0; s1 = left->s1 + right->s1; if (s0 >= mod) s0 -= mod; if (s1 >= mod) s1 -= mod; } }; st medis; void init(int N_, int M_, vector<int> P_, vector<int> A_) { P = P_; A = A_; N = N_; M = M_; c = vector<vector<int>>(N + M); for (int i = 1; i < N + M; i++) c[P[i]].push_back(i); ll prod[N + M]; { function<void(int)>dfs = [&](int i)->void { prod[i] = max(1, (int)c[i].size()); for (int j : c[i]) { dfs(j); prod[i] *= prod[j]; prod[i] %= mod; } }; dfs(0); } D = vector<int>(N + M); { function<void(int, ll)>dfs = [&](int i, ll ss)->void { D[i] = (int)ss; vector<ll>s; int cnt = 0; for (int j : c[i]) { s.push_back(prod[j]); cnt++; } vector<ll>t = s; reverse(t.begin(), t.end()); s.insert(s.begin(), 1); t.insert(t.begin(), 1); for (int i = 1; i < (int)s.size(); i++) s[i] = (s[i - 1] * s[i]) % mod; for (int i = 1; i < (int)t.size(); i++) t[i] = (t[i - 1] * t[i]) % mod; int k = 0; for (int j : c[i]) { ll s_ = ss; s_ *= s[k]; s_ %= mod; s_ *= t[cnt - 1 - k]; s_ %= mod; dfs(j, s_); k++; } }; dfs(0, 1); } medis = st(0, M - 1); } int count_ways(int X, int Y) { medis.fl(X - N, Y - N); return medis.s1; }
#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...