제출 #1264872

#제출 시각아이디문제언어결과실행 시간메모리
1264872silentloop디지털 회로 (IOI22_circuit)C++20
7 / 100
3025 ms12884 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], hijos[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]}; vector<ll> a(hijos[nod], 0); a[0] = 1; pair<ll, ll> cant = {-1, 0}; ll i=0; for (auto k : grafo[nod]) { i++; pair<ll, ll> ret = dfs(k); pair<ll, ll> un = {0,0}; if (cant.fr == -1) { cant = ret; continue; } un.fr=(i*(cant.fr*ret.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) un.fr=(un.fr+(cant.fr*ret.se)%MOD)%MOD; // solo el de la izquierda activo un.fr=(un.fr+(ret.fr*cant.se)%MOD)%MOD; // solo el de la derecha activo un.se=(i*(cant.se*ret.se)%MOD)%MOD; // los 2 apagados un.se=(un.se+(cant.fr*ret.se)%MOD)%MOD; // solo 1 activo con al menos 2 activos un.se=(un.se+(cant.se*ret.fr)%MOD)%MOD; // solo 1 activo con al menos 2 activos cant=un; } return cant; } void calc() { pair<ll, ll> a = dfs(0); tot = a.fr; } ll in(ll nod) { hijos[nod] = 1; for (auto k : grafo[nod]) { hijos[nod] += in(k); } return hijos[nod]; } 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]; in(0); 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...