제출 #1264905

#제출 시각아이디문제언어결과실행 시간메모리
1264905silentloop디지털 회로 (IOI22_circuit)C++20
18 / 100
3098 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: ways activo (state=1), se: ways apagado (state=0) if (nod >= n) { return {val[nod], 1 - val[nod]}; } vector<pair<ll, ll>> children_ways; for (auto k : grafo[nod]) { auto p = dfs(k); children_ways.pb(p); } int c = sz(children_ways); if (c == 0) { return {0, 0}; } vector<ll> S(c); for (int i = 0; i < c; i++) { S[i] = (children_ways[i].fr + children_ways[i].se) % MOD; } // Productos prefijo (left: prod j=0 to i-1) vector<ll> left(c); left[0] = 1; for (int i = 1; i < c; i++) { left[i] = left[i - 1] * S[i - 1] % MOD; } // Productos sufijo (right: prod j=i+1 to c-1) vector<ll> right(c); right[c - 1] = 1; for (int i = c - 2; i >= 0; i--) { right[i] = right[i + 1] * S[i + 1] % MOD; } // Calcular on ll onn = 0; for (int i = 0; i < c; i++) { ll prod_others = left[i] * right[i] % MOD; onn = (onn + children_ways[i].fr * prod_others % MOD) % MOD; } // Calcular full_prod = prod all S ll full_prod = 1; for (auto s : S) { full_prod = full_prod * s % MOD; } // off = c * full_prod - onn ll off = ((ll)c * full_prod % MOD - onn + MOD) % MOD; return {onn, off}; } 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...