Submission #826162

#TimeUsernameProblemLanguageResultExecution timeMemory
826162PixelCatDigital Circuit (IOI22_circuit)C++17
0 / 100
430 ms8272 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]; void dfs(int x) { if(x >= n) { s[x] = 1; return; } s[x] = sz(adj[x]); for(auto &i:adj[x]) { dfs(i); s[x] = s[x] * s[i] % MOD; } } int ss[MAXN + 10]; void dfs2(int x, int owo) { if(x >= n) { ss[x] = owo; return; } int l = adj[x][0]; int r = adj[x][1]; dfs2(l, owo * s[r] % MOD); dfs2(r, owo * s[l] % MOD); } int ans = 0; void update_leaf(int pos, int val) { ans = ((ans + val * ss[pos]) % MOD + MOD) % MOD; } 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, A[i]); } } i32 count_ways(i32 L, i32 R) { int na = 1 - a[L]; update_leaf(L, na - a[L]); return ans; } /* 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...