Submission #826154

#TimeUsernameProblemLanguageResultExecution timeMemory
826154PixelCatDigital Circuit (IOI22_circuit)C++17
4 / 100
794 ms13204 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 = 200'000; const int MOD = 1'000'002'022; int n, m; vector<int> adj[MAXN + 10]; int p[MAXN + 10]; int a[MAXN + 10]; int s[MAXN + 10]; int xs[MAXN + 10]; void dfs(int x) { if(x >= n) { s[x] = 1; return; } xs[x] = 0; s[x] = sz(adj[x]); for(auto &i:adj[x]) { dfs(i); s[x] = s[x] * s[i] % MOD; xs[x] ^= s[i]; } } int ss[MAXN + 10]; void dfs2(int x, int owo) { if(x >= n) { ss[x] = owo; return; } for(auto &i:adj[x]) { dfs2(i, (owo * (xs[x] ^ s[i])) % MOD); } } int dp[MAXN + 10]; void update(int x) { if(x >= n) { dp[x] = a[x]; return; } int l = adj[x][0]; int r = adj[x][1]; dp[x] = (s[l] * dp[r] + s[r] * dp[l]) % MOD; } void update_leaf(int x) { update(x); while(x != 0) { x = p[x]; update(x); } } void init(i32 N, i32 M, std::vector<i32> P, std::vector<i32> A) { n = N; m = M; p[0] = -1; For(i, 1, n + m - 1) { adj[P[i]].eb(i); p[i] = P[i]; } dfs(0); dfs2(0, 1); For(i, 0, m - 1) { a[n + i] = A[i]; update_leaf(n + i); } } i32 count_ways(i32 L, i32 R) { a[L] = 1 - a[L]; update_leaf(L); return dp[0]; } /* 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...