Submission #1264919

#TimeUsernameProblemLanguageResultExecution timeMemory
1264919silentloopDigital Circuit (IOI22_circuit)C++20
9 / 100
3044 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 tot = 1; vector<pair<ll, ll>> s; vector<ll> pref, suf; for (auto k : grafo[nod]) { pair<ll, ll> a = dfs(k); s.pb(a); tot = (tot * (a.fr + a.se) % MOD) % MOD; } int c = sz(s); // Número de hijos pref.resize(c); pref[0] = 1; suf.resize(c); suf[c - 1] = 1; for (int i = 1; i < c; i++) pref[i] = (pref[i - 1] * (s[i - 1].fr + s[i - 1].se) % MOD) % MOD; for (int i = c - 2; i >= 0; i--) suf[i] = (suf[i + 1] * (s[i + 1].fr + s[i + 1].se) % MOD) % MOD; for (int i = 0; i < c; i++) cant.fr = (cant.fr + (s[i].fr * (pref[i] * suf[i]) % MOD) % MOD) % MOD; cant.se = ((tot * (ll)c % MOD) - cant.fr + MOD) % MOD; // Corrección: todo en una línea 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...