제출 #807599

#제출 시각아이디문제언어결과실행 시간메모리
807599Ozy디지털 회로 (IOI22_circuit)C++17
18 / 100
18 ms2160 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; #define lli long long int #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define rep(i,a,b) for(int i = (a); i <= (b); i++) #define repa(i,a,b) for(int i = (a); i >= (b); i--) #define pll pair<lli,lli> #define MAX 2000 #define mod 1000002022 //para el arreglo #define unos first #define ceros second vector<lli> hijos[MAX+2]; lli n,m; lli dp[MAX+2][MAX+2]; pll arr[MAX+2]; pll solve(lli pos) { pll res = {0,0}; lli sig,apu = 0; lli tam = hijos[pos].size(); rep(i,0,tam) dp[apu][i] = 0; dp[apu][0] = 1; for(auto h : hijos[pos]) { sig = apu^1; rep(i,0,tam) dp[sig][i] = 0; rep(i,0,tam) { dp[sig][i] += dp[apu][i] * arr[h].ceros; dp[sig][i+1] += dp[apu][i] * arr[h].unos; } rep(i,0,tam) dp[sig][i] %= mod; apu = sig; } lli u = 0; lli c = tam; rep(i,0,tam) { res.unos += dp[apu][i]*u; res.ceros += dp[apu][i]*c; u++; c--; } res.unos %= mod; res.ceros %= mod; return res; } void init(int N, int M, std::vector<int> P, std::vector<int> A) { n = N; m=M; rep(i,1,N+M-1) hijos[P[i]].push_back(i); rep(i,0,M-1) { if (A[i] == 0) arr[i+n] = {0,1}; else arr[i+n] = {1,0}; } repa(i,n-1,0) arr[i] = solve(i); } int count_ways(int L, int R) { rep(i,L,R) { arr[i].unos ^= 1; arr[i].ceros ^= 1; } repa(i,n-1,0) arr[i] = solve(i); return arr[0].unos; }
#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...