Submission #1024788

#TimeUsernameProblemLanguageResultExecution timeMemory
1024788aibarkDigital Circuit (IOI22_circuit)C++17
2 / 100
418 ms17396 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; const int NN = (int)2e5 + 123, mod = (int)1e9 + 2022; int n, m; vector<int> p, a; vector<int> g[NN]; long long sz[NN], ans[NN]; void dfs(int v) { sz[v] = max(1, (int)g[v].size()); for (int to : g[v]) { dfs(to); sz[v] = sz[v] * sz[to] % mod; } } void dfs1(int v) { long long A = ans[v]; for (int to : g[v]) { ans[to] = A; A = A * sz[to] % mod; } A = 1; reverse(g[v].begin(), g[v].end()); for (int to : g[v]) { ans[to] = ans[to] * A % mod; A = A * sz[to] % mod; } for (int to : g[v]) dfs1(to); } long long t[2][4 * NN]; int add[4 * NN]; void build(int v, int tl, int tr) { if (tl == tr) { t[1][v] = ans[tl + n]; t[0][v] = 0; if (a[tl] == 0) swap(t[1][v], t[0][v]); return; } int tm = (tl + tr) >> 1; build(v + v, tl, tm); build(v + v + 1, tm + 1, tr); t[1][v] = t[1][v + v] + t[1][v + v + 1]; t[0][v] = t[0][v + v] + t[0][v + v + 1]; } void push(int v) { if (add[v]) { add[v + v] ^= 1; add[v + v + 1] ^= 1; swap(t[0][v + v], t[1][v + v]); swap(t[0][v + v + 1], t[1][v + v + 1]); add[v] = 0; } } void upd(int v, int tl, int tr, int l, int r) { if (tr < l || r < tl) return; if (l <= tl && tr <= r) { swap(t[0][v], t[1][v]); add[v] ^= 1; return; } push(v); int tm = (tl + tr) >> 1; upd(v + v, tl, tm, l, r); upd(v + v + 1, tm + 1, tr, l, r); t[1][v] = t[1][v + v] + t[1][v + v + 1]; t[0][v] = t[0][v + v] + t[0][v + v + 1]; } void init(int N, int M, vector<int> P, vector<int> A) { n = N, m = M; p = P, a = A; for (int i = 1; i < n + m; i++) g[p[i]].push_back(i); dfs(0); ans[0] = 1; dfs1(0); build(1, 0, m - 1); } int count_ways(int L, int R) { // long long ansa = 0; // for (int i = L; i <= R; i++) // a[i - n] ^= 1; // for (int i = n; i < n + m; i++) { // // cout << i << " " << a[i - n] << " " << ans[i] << endl; // ansa = ansa + a[i - n] * ans[i]; // } // return ansa; upd(1, 0, m - 1, L - n, R - n); 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...