제출 #1264928

#제출 시각아이디문제언어결과실행 시간메모리
1264928silentloopDigital Circuit (IOI22_circuit)C++20
0 / 100
1556 ms1889820 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 = 2e1 + 1; const int MOD = 1000002022; vector<ll> grafo[MAXN]; ll val[MAXN], p[MAXN]; ll n, m, tot = 0; pair<ll, ll> memo[MAXN]; pair<ll, ll> dfs(ll nod) // fr: posibilidades activo, se: posibilidades apagado { if (nod >= n) { memo[nod]={val[nod], !val[nod]}; return memo[nod]; } pair<ll, ll> cant = {0, 0}, iz = dfs(grafo[nod][0]), der = dfs(grafo[nod][1]); cant.fr = (2ll * (iz.fr * der.fr) % MOD) % MOD; // los dos en 1 (*2 pq se puede dejar en 1 con al menos 1 activo y con al menos 2 activos) cant.fr = (cant.fr + (iz.fr * der.se) % MOD) % MOD; // solo el de la izquierda activo cant.fr = (cant.fr + (der.fr * iz.se) % MOD) % MOD; // solo el de la derecha activo cant.se = (2ll * (iz.se * der.se) % MOD) % MOD; // los 2 apagados cant.se = (cant.se + (iz.fr * der.se) % MOD) % MOD; // solo 1 activo con al menos 2 activos cant.se = (cant.se + (iz.se * der.fr) % MOD) % MOD; // solo 1 activo con al menos 2 activos memo[nod] = cant; 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; p[0] = -1; for (i = 1; i < sz(P); i++) { p[i] = P[i]; grafo[P[i]].pb(i); } for (i = 0; i < sz(A); i++) val[i + N] = A[i]; n = N; m = M; calc(); } void update(ll x) { if (x == -1) return; pair<ll, ll> cant = {0, 0}, iz = memo[grafo[x][0]], der = memo[grafo[x][1]]; cant.fr = (2ll * (iz.fr * der.fr) % MOD) % MOD; // los dos en 1 (*2 pq se puede dejar en 1 con al menos 1 activo y con al menos 2 activos) cant.fr = (cant.fr + (iz.fr * der.se) % MOD) % MOD; // solo el de la izquierda activo cant.fr = (cant.fr + (der.fr * iz.se) % MOD) % MOD; // solo el de la derecha activo cant.se = (2ll * (iz.se * der.se) % MOD) % MOD; // los 2 apagados cant.se = (cant.se + (iz.fr * der.se) % MOD) % MOD; // solo 1 activo con al menos 2 activos cant.se = (cant.se + (iz.se * der.fr) % MOD) % MOD; // solo 1 activo con al menos 2 activos memo[x] = cant; update(p[x]); } int count_ways(int L, int R) { ll i; for(i=L; i<=R; i++) { val[i] = !val[i]; memo[i]={val[i], !val[i]}; update(p[i]); } return memo[0].fr; }
#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...