Submission #826035

#TimeUsernameProblemLanguageResultExecution timeMemory
826035PixelCatDigital Circuit (IOI22_circuit)C++17
0 / 100
602 ms5100 KiB
#include "circuit.h" #ifdef NYAOWO #include "stub.cpp" #endif #include <bits/stdc++.h> #define For(i, a, b) for(int i = a; i <= b; i++) #define Forr(i, a, b) for(int i = a; i >= b; i--) #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) ((int)x.size()) #define eb emplace_back #define int LL using namespace std; using i32 = int32_t; using LL = long long; using pii = pair<int, int>; const int MAXN = 100'000; const int MOD = 1'000'002'022; int n, m; vector<int> adj[MAXN + 10]; int dp[MAXN + 10][2]; int flip[MAXN + 10]; void update(int x) { vector<int> v(1, 1); for(auto &child:adj[x]) { vector<int> v2; v2.eb(v[0] * dp[child][0] % MOD); For(i, 1, sz(v) - 1) { v2.eb((v[i] * dp[child][0] + v[i - 1] * dp[child][1]) % MOD); } v2.eb(v.back() * dp[child][1] % MOD); v.swap(v2); } dp[x][0] = dp[x][1] = 0; int c = sz(adj[x]); For(i, 0, c) { dp[x][0] = (dp[x][0] + v[i] * (c - i)) % MOD; dp[x][1] = (dp[x][1] + v[i] * i) % MOD; } if(flip[x]) swap(dp[x][0], dp[x][1]); } void init(i32 N, i32 M, std::vector<i32> P, std::vector<i32> A) { n = N; m = M; For(i, 1, n + m - 1) { adj[P[i]].eb(i); } For(i, 0, m - 1) { int x = A[i]; dp[n + i][x] = 1; dp[n + i][1 - x] = 0; } } #define L(id) ((id) * 2 + 1) #define R(id) ((id) * 2 + 2) void range_flip(int id, int l, int r, int L, int R) { if(l >= L && r <= R) { flip[id] ^= 1; update(id); return; } int mi = (l + r) / 2; if(L <= mi) range_flip(L(id), l, mi, L, R); if(R > mi) range_flip(R(id), mi + 1, r, L, R); update(id); } i32 count_ways(i32 L, i32 R) { int i = L; swap(dp[i][0], dp[i][1]); while(i) { i = (i - 1) / 2; update(i); } return (i32)dp[0][1]; } /* 3 4 3 -1 0 1 2 1 1 0 1 0 1 0 3 4 4 5 3 6 2 0 6 */
#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...