Submission #1264918

#TimeUsernameProblemLanguageResultExecution timeMemory
1264918silentloopDigital Circuit (IOI22_circuit)C++20
9 / 100
3015 ms7044 KiB
#include <bits/stdc++.h> #define ll long long #define sz(x) int(x.size()) #define forn(i, n) for (i = 0; i < n; i++) #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair #define fr first #define se second using namespace std; const int MAXN = 2e5 + 1; const int MOD = 1000002022; vector<ll> grafo[MAXN]; ll val[MAXN]; ll n, m, tot = 0; pair<ll, ll> dfs(ll nod) // fr: posibilidades activo, se: posibilidades apagado { if (nod >= n) return {val[nod], !val[nod]}; pair<ll, ll> cant = {0, 0}; ll i=0, tot=1; vector<pair<ll,ll>>s; vector<ll>pref,suf; for (auto k : grafo[nod]) { i++; pair<ll,ll>a=dfs(k); s.pb(a); tot=(tot*(a.fr+a.se)%MOD)%MOD; } pref.resize(sz(s)); pref[0]=1; suf.resize(sz(s)); suf[sz(suf)-1]=1; for(i=1; i<sz(s); i++) pref[i]=(pref[i-1]*(s[i-1].fr+s[i-1].se)%MOD)%MOD; for(i=sz(s)-2; i>=0; i--) suf[i]=(suf[i+1]*(s[i+1].fr+s[i+1].se)%MOD)%MOD; for(i=0; i<sz(s); i++) cant.fr=(cant.fr+(s[i].fr*(pref[i]*suf[i])%MOD)%MOD)%MOD; cant.se = (tot * (ll)sz(grafo[nod]) % MOD - cant.fr + MOD) % MOD; return cant; } void calc() { pair<ll, ll> a = dfs(0); tot = a.fr; } void init(int N, int M, std::vector<int> P, std::vector<int> A) { ll i; for (i = 1; i < sz(P); i++) grafo[P[i]].pb(i); for (i = 0; i < sz(A); i++) val[i + N] = A[i]; n = N; m = M; } int count_ways(int L, int R) { ll i; for (i = L; i <= R; i++) val[i] = !val[i]; calc(); return tot; }
#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...