Submission #1079844

#TimeUsernameProblemLanguageResultExecution timeMemory
1079844LittleOrangeDigital Circuit (IOI22_circuit)C++17
18 / 100
3055 ms3672 KiB
#include "circuit.h" #include <vector> #include<bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 1000002022; ll n,m; vector<ll> p,a; vector<vector<ll>> con; void init(int N, int M, std::vector<int> P, std::vector<int> A) { n=N; m=M; p.assign(P.begin(),P.end()); a.assign(A.begin(),A.end()); con.resize(n); for(ll i = 1;i<n+m;i++) con[p[i]].push_back(i); } pair<ll,ll> dfs(ll i){// 0, 1 if (i>=n) return {a[i-n]==0,a[i-n]==1}; ll c = con[i].size(); vector<ll> v(c+1,0),v0(c+1,0); v[0] = 1; for(ll j : con[i]){ auto [x,y] = dfs(j); for(ll i = 0;i<c;i++){ v0[i] += v[i]*x%mod; v0[i+1] += v[i]*y%mod; } v.swap(v0); fill(v0.begin(),v0.end(),0); } ll x = 0, y = 0; for(ll j = 0;j<=c;j++){ x += v[j]*(c-j)%mod; y += v[j]*j%mod; } return {x%mod,y%mod}; } int count_ways(int L, int R) { for(ll i = L;i<=R;i++) a[i-n]^=1; return dfs(0).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...