Submission #793139

#TimeUsernameProblemLanguageResultExecution timeMemory
793139SlavicGDigital Circuit (IOI22_circuit)C++17
9 / 100
3057 ms8996 KiB
#include <bits/stdc++.h> #include "circuit.h" using namespace std; const int N = 2e5 + 5, mod = 1000002022; vector<int> adj[N]; int64_t dp[N][2], color[N]; void dfs(int u) { if(adj[u].size() == 0) { if(color[u]) dp[u][0] = 0, dp[u][1] = 1; else dp[u][0] = 1, dp[u][1] = 0; return; } for(int v: adj[u]) dfs(v); vector<vector<int>> D((int)adj[u].size() + 1, vector<int>((int)adj[u].size() + 1)); D[0][0] = 1; for(int i = 0; i < (int)adj[u].size(); ++i) { for(int j = 0; j <= i; ++j) { D[i + 1][j] += D[i][j] * dp[adj[u][i]][0] % mod; D[i + 1][j] %= mod; D[i + 1][j + 1] += D[i][j] * dp[adj[u][i]][1] % mod; D[i + 1][j + 1] %= mod; } } dp[u][0] = dp[u][1] = 0; for(int i = 0; i <= (int)adj[u].size(); ++i) { dp[u][1] += D[(int)adj[u].size()][i] * i % mod; dp[u][1] %= mod; dp[u][0] += D[(int)adj[u].size()][i] * ((int)adj[u].size() - i) % mod; dp[u][0] %= mod; } } void init(int N, int M, std::vector<int> P, std::vector<int> A) { for(int i = 1; i < N + M; ++i) { adj[P[i]].push_back(i); } for(int i = 0; i < M; ++i) color[i + N] = A[i]; dfs(0); } int count_ways(int L, int R) { for(int i = L; i <= R; ++i) { color[i] ^= 1; } dfs(0); return dp[0][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...