Submission #627713

#TimeUsernameProblemLanguageResultExecution timeMemory
627713dqhungdlDigital Circuit (IOI22_circuit)C++17
4 / 100
1030 ms29592 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; const int MAX = 2e5 + 5, MOD = 1e9 + 2022; int N; long long C[MAX], f[MAX]; vector<long long> g[MAX]; struct SegmentTree { int n; vector<vector<long long>> tree; vector<int> lazy; SegmentTree() {} SegmentTree(int _n, vector<vector<long long>> &V) { n = _n; tree.resize(4 * n + 5, {0, 0}); lazy.resize(4 * n + 5); init(1, 0, n - 1, V); } void init(int k, int l, int r, vector<vector<long long>> &V) { if (l == r) { tree[k] = V[l]; return; } int mid = (l + r) / 2; init(2 * k, l, mid, V); init(2 * k + 1, mid + 1, r, V); for (int i = 0; i <= 1; i++) tree[k][i] = (tree[2 * k][i] + tree[2 * k + 1][i]) % MOD; } void down(int k) { if (lazy[k]) { lazy[2 * k] ^= lazy[k], lazy[2 * k + 1] ^= lazy[k]; if (lazy[2 * k]) swap(tree[2 * k][0], tree[2 * k][1]); if (lazy[2 * k + 1]) swap(tree[2 * k + 1][0], tree[2 * k + 1][1]); lazy[k] = 0; } } void update(int k, int l, int r, int L, int R) { if (l > R || L > r) return; if (L <= l && r <= R) { swap(tree[k][0], tree[k][1]); lazy[k] ^= 1; return; } down(k); int mid = (l + r) / 2; update(2 * k, l, mid, L, R); update(2 * k + 1, mid + 1, r, L, R); for (int i = 0; i <= 1; i++) tree[k][i] = (tree[2 * k][i] + tree[2 * k + 1][i]) % MOD; } void update(int L, int R) { update(1, 0, n - 1, L, R); } } tree; void dfs(int u) { if (g[u].empty()) { C[u] = 1; return; } C[u] = g[u].size(); for (int v: g[u]) { dfs(v); C[u] = C[u] * C[v] % MOD; } vector<long long> L(g[u].size()), R(g[u].size()); L[0] = C[g[u][0]]; for (int i = 1; i < g[u].size(); i++) L[i] = L[i - 1] * C[g[u][i]] % MOD; R.back() = C[g[u].back()]; for (int i = (int) g[u].size() - 2; i >= 0; i--) R[i] = R[i + 1] * C[g[u][i]] % MOD; for (int i = 0; i < g[u].size(); i++) { long long left = i ? L[i - 1] : 1; long long right = i < g[u].size() - 1 ? R[i + 1] : 1; f[g[u][i]] = left * right % MOD; } } void init(int _N, int M, vector<int> P, vector<int> A) { N = _N; for (int i = 1; i < N + M; i++) g[P[i]].push_back(i); dfs(0); f[0] = 1; for (int i = 1; i < N + M; i++) f[i] = f[i] * f[P[i]] % MOD; vector<vector<long long>> V(M); for (int i = 0; i < M; i++) if (A[i]) V[i] = {0, f[i + N]}; else V[i] = {f[i + N], 0}; tree = SegmentTree(M, V); } int count_ways(int L, int R) { tree.update(L - N, R - N); return tree.tree[1][1]; } //int main() { // freopen("../_input", "r", stdin); // int N, M, Q; // assert(3 == scanf("%d %d %d", &N, &M, &Q)); // std::vector<int> P(N + M), A(M); // for (int i = 0; i < N + M; ++i) { // assert(1 == scanf("%d", &P[i])); // } // for (int j = 0; j < M; ++j) { // assert(1 == scanf("%d", &A[j])); // } // init(N, M, P, A); // // for (int i = 0; i < Q; ++i) { // int L, R; // assert(2 == scanf("%d %d", &L, &R)); // printf("%d\n", count_ways(L, R)); // } // return 0; //}

Compilation message (stderr)

circuit.cpp: In function 'void dfs(int)':
circuit.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 1; i < g[u].size(); i++)
      |                     ~~^~~~~~~~~~~~~
circuit.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < g[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
circuit.cpp:88:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         long long right = i < g[u].size() - 1 ? R[i + 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...