Submission #780360

#TimeUsernameProblemLanguageResultExecution timeMemory
780360mousebeaverDigital Circuit (IOI22_circuit)C++17
18 / 100
3090 ms4152 KiB
#define ll long long #define pll pair<ll, ll> #define MOD 1000002022 #include "circuit.h" #include <bits/stdc++.h> using namespace std; ll n = 0; vector<ll> a(0); vector<vector<ll>> adjlist(0); void init(int N, int M, std::vector<int> P, std::vector<int> A) { n = N+M; adjlist.assign(n, vector<ll> (0)); for(ll i = 1; i < n; i++) { adjlist[P[i]].push_back(i); } a.assign(n, 0); for(ll i = N; i < n; i++) { a[i] = A[i-N]; } } pll dfs(int i) //On, off { if(adjlist[i].empty()) { return {a[i], 1-a[i]}; } ll c = adjlist[i].size(); ll all = c; vector<ll> dp(c+1, 0); //Possibilities for being on dp[0] = 1; for(ll j : adjlist[i]) { pll p = dfs(j); all = (all * ((p.first+p.second)%MOD))%MOD; vector<ll> postdp(c+1, 0); for(ll k = 0; k <= c; k++) { postdp[k] = (dp[k]*p.second)%MOD; if(k > 0) { postdp[k] = (postdp[k] + (dp[k-1]*p.first)%MOD)%MOD; } } dp = postdp; } ll on = 0; for(ll k = c; k > 0; k--) { on = (on+((dp[k]*k)%MOD))%MOD; } return {on, (all+MOD-on)%MOD}; } int count_ways(int L, int R) { for(ll i = L; i <= R; i++) { a[i] = 1-a[i]; } return dfs(0).first; }
#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...