Submission #1034237

#TimeUsernameProblemLanguageResultExecution timeMemory
1034237Mr_HusanboyDigital Circuit (IOI22_circuit)C++17
18 / 100
3059 ms4184 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define all(a) (a).begin(), (a).end() #define ll long long const int mod = 1000002022; vector<int> state, p; int n, m; vector<vector<int>> g; template<typename T> int len(T &a){return a.size();} vector<array<ll, 2>> dp; void init(int N, int M, std::vector<int> P, std::vector<int> A) { n = N, m = M; g.resize(n); state = A; p = P; for(int i = 1; i < n + m; i ++){ g[p[i]].push_back(i); } dp.resize(n + m); } void dfs(int i){ if(i >= n){ dp[i][0] = state[i - n] ^ 1; dp[i][1] = state[i - n]; return; } for(auto u : g[i]) dfs(u); vector<ll> prep(len(g[i]) + 1); prep[0] = 1; ll al = len(g[i]); int cur = 0; for(auto u : g[i]){ cur ++; al = al * (dp[u][0] + dp[u][1]) % mod; for(int j = cur; j >= 0; j --){ prep[j] = prep[j] * dp[u][0] % mod; if(j) prep[j] += prep[j - 1] * dp[u][1] % mod; } } dp[i][1] = 0; for(int j = 1; j <= len(g[i]); j ++){ //cout << prep[j] * j << endl; dp[i][1] = (dp[i][1] + prep[j] * j) % mod; } dp[i][0] = al - dp[i][1]; if(dp[i][0] < 0) dp[i][0] += mod; } int count_ways(int l, int r) { l -= n; r -= n; for(int i = l; i <= r; i ++) state[i] ^= 1; //for(int i = 0; i < m; i ++) cout << state[i] << ' '; 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...