Submission #1058532

#TimeUsernameProblemLanguageResultExecution timeMemory
1058532SalihSahinDigital Circuit (IOI22_circuit)C++17
18 / 100
3007 ms2388 KiB
#include<bits/stdc++.h> #define pb push_back using namespace std; #include "circuit.h" #define ll long long const int M = 2000; ll mod = 1000002022; int add(ll a, ll b){ return ((a%mod) + (b%mod))%mod; } int mul(ll a, ll b){ return ((a%mod) * (b%mod))%mod; } vector<int> state(M); vector<int> ch[2 * M]; int n; pair<int, int> dfs(int node){ // {kac sekilde 0, kac sekilde 1} if(node >= n){ if(state[node - n]) return {0, 1}; else return {1, 0}; } vector<pair<int, int> > sub; int c = ch[node].size(); for(auto itr: ch[node]){ sub.pb(dfs(itr)); } vector<ll> dp(c+1), ndp(c+1); dp[0] = 1; for(auto itr: sub){ for(int i = 0; i <= c; i++){ ndp[i] = mul(dp[i], itr.first); if(i) ndp[i] = add(ndp[i], mul(dp[i-1], itr.second)); } dp = ndp; } pair<ll, ll> val; for(int i = 1; i <= c; i++){ for(int j = 0; j <= c; j++){ if(i > j) val.first = add(val.first, dp[j]); else val.second = add(val.second, dp[j]); } } return val; } void init(int N, int M, std::vector<int> P, std::vector<int> A) { n = N; for(int i = 1; i < N + M; i++){ ch[P[i]].pb(i); } for(int i = 0; i < M; i++) state[i] = A[i]; return; } int count_ways(int L, int R) { L -= n; R -= n; for(int i = L; i <= R; i++){ state[i] ^= 1; } pair<ll, ll> ans = dfs(0); return ans.second; }
#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...