Submission #757164

#TimeUsernameProblemLanguageResultExecution timeMemory
757164boris_mihovDigital Circuit (IOI22_circuit)C++17
100 / 100
1278 ms48376 KiB
#include "circuit.h" #include <algorithm> #include <iostream> #include <numeric> #include <vector> typedef long long llong; const int MAXN = 200000 + 10; const int MOD = 1000002022; const int INF = 1e9; int n, m; struct SegmentTree { struct Node { llong realVal, swapVal; bool lazy; Node() { realVal = swapVal = lazy = 0; } }; Node tree[2*MAXN]; // 2 * MAXN * 2 Node combine(Node left, Node right) { Node res; res.realVal = left.realVal + right.realVal; res.swapVal = left.swapVal + right.swapVal; if (res.realVal >= MOD) res.realVal -= MOD; if (res.swapVal >= MOD) res.swapVal -= MOD; return res; } void push(int node, int l, int r) { if (!tree[node].lazy) { return; } std::swap(tree[node].realVal, tree[node].swapVal); if (l < r) { tree[2*node].lazy ^= 1; tree[2*node + 1].lazy ^= 1; } tree[node].lazy = 0; } void build(int l, int r, int node, llong vals[], llong b[]) { if (l == r) { tree[node].realVal = vals[n + l]; tree[node].swapVal = 0; if (b[n + l] == 0) { std::swap(tree[node].realVal, tree[node].swapVal); } return; } int mid = (l + r) / 2; build(l, mid, 2*node, vals, b); build(mid + 1, r, 2*node + 1, vals, b); tree[node] = combine(tree[2*node], tree[2*node + 1]); } void update(int l, int r, int node, int queryL, int queryR) { push(node, l, r); if (queryR < l || r < queryL) { return; } if (queryL <= l && r <= queryR) { tree[node].lazy ^= 1; push(node, l, r); return; } int mid = (l + r) / 2; update(l, mid, 2*node, queryL, queryR); update(mid + 1, r, 2*node + 1, queryL, queryR); tree[node] = combine(tree[2*node], tree[2*node + 1]); } void build(llong multBy[], llong b[]) { build(1, m, 1, multBy, b); } llong query(int l, int r) { update(1, m, 1, l - n + 1, r - n + 1); return tree[1].realVal; } }; llong w[MAXN]; llong b[MAXN]; llong pw[MAXN]; llong multBy[MAXN]; std::vector <int> g[MAXN]; std::vector <int> prefixPW[MAXN]; std::vector <int> suffixPW[MAXN]; SegmentTree tree; void initDFS(int node) { if (g[node].empty()) { pw[node] = 1; return; } pw[node] = g[node].size(); for (const int &i : g[node]) { initDFS(i); pw[node] *= pw[i]; pw[node] %= MOD; } prefixPW[node].resize(g[node].size()); prefixPW[node][0] = 1; for (int i = 1 ; i < g[node].size() ; ++i) { prefixPW[node][i] = (prefixPW[node][i - 1] * pw[g[node][i - 1]]) % MOD; } suffixPW[node].resize(g[node].size()); suffixPW[node][g[node].size() - 1] = 1; for (int i = (int)g[node].size() - 2 ; i >= 0 ; --i) { suffixPW[node][i] = (suffixPW[node][i + 1] * pw[g[node][i + 1]]) % MOD; } } void findMult(int node, llong mult) { if (g[node].empty()) { multBy[node] = mult; return; } for (int i = 0 ; i < g[node].size() ; ++i) { findMult(g[node][i], (((mult * prefixPW[node][i]) % MOD) * suffixPW[node][i]) % MOD); } } void init(int N, int M, std::vector <int> P, std::vector <int> A) { n = N; m = M; for (int i = 1 ; i < n + m ; ++i) { g[P[i] + 1].push_back(i + 1); } for (int i = n + 1 ; i <= n + m ; ++i) { if (A[i - n - 1] == 0) { w[i] = 1; b[i] = 0; } else { b[i] = 1; w[i] = 0; } } initDFS(1); findMult(1, 1); tree.build(multBy, b); } int count_ways(int L, int R) { return tree.query(L, R); }

Compilation message (stderr)

circuit.cpp: In function 'void initDFS(int)':
circuit.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for (int i = 1 ; i < g[node].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~
circuit.cpp: In function 'void findMult(int, llong)':
circuit.cpp:158:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for (int i = 0 ; i < g[node].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~~
#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...