이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |