#define ll long long
#define pll pair<ll, ll>
#define MOD 1000002022
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
bool subFirst = false;
ll n = 0;
vector<ll> a(0);
vector<vector<ll>> adjlist(0);
pll dfsSubFirst(int i) //On, off
{
if(adjlist[i].empty())
{
return {a[i], 1-a[i]};
}
ll c = adjlist[i].size();
ll all = c;
vector<ll> dp(c+1, 0); //Possibilities for being on
dp[0] = 1;
for(ll j : adjlist[i])
{
pll p = dfsSubFirst(j);
all = (all * ((p.first+p.second)%MOD))%MOD;
vector<ll> postdp(c+1, 0);
for(ll k = 0; k <= c; k++)
{
postdp[k] = (dp[k]*p.second)%MOD;
if(k > 0)
{
postdp[k] = (postdp[k] + (dp[k-1]*p.first)%MOD)%MOD;
}
}
dp = postdp;
}
ll on = 0;
for(ll k = c; k > 0; k--)
{
on = (on+((dp[k]*k)%MOD))%MOD;
}
return {on, (all+MOD-on)%MOD};
}
struct node
{
ll on = 0;
ll off = 0;
bool flip = false;
ll left = -1;
ll right = -1;
};
vector<node> s(0);
void update(ll i)
{
if(s[i].flip)
{
swap(s[i].on, s[i].off);
if(s[i].left != -1)
{
s[s[i].left].flip = !s[s[i].left].flip;
s[s[i].right].flip = !s[s[i].right].flip;
}
s[i].flip = false;
}
}
void apply(ll i, ll L, ll R, ll a, ll b)
{
if(L <= a && b <= R)
{
s[i].flip = !s[i].flip;
}
update(i);
if(!(L <= a && b <= R) && !(R < a || b < L))
{
ll mid = (a+b)/2;
apply(s[i].left, L, R, a, mid);
apply(s[i].left, L, R, a, mid);
}
ll l = s[i].left;
ll r = s[i].right;
s[i].on = (2*s[l].on*s[r].on)%MOD;
s[i].on += (s[l].on*s[r].off)%MOD;
s[i].on %= MOD;
s[i].on += (s[l].off*s[r].off)%MOD;
s[i].on %= MOD;
s[i].off = (2*s[l].off*s[r].off)%MOD;
s[i].off += (s[l].on*s[r].off)%MOD;
s[i].off %= MOD;
s[i].off += (s[l].off*s[r].off)%MOD;
s[i].off %= MOD;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
n = N+M;
subFirst = (N <= 1000 && M <= 1000);
if(subFirst)
{
adjlist.assign(n, vector<ll> (0));
for(ll i = 1; i < n; i++)
{
adjlist[P[i]].push_back(i);
}
a.assign(n, 0);
for(ll i = N; i < n; i++)
{
a[i] = A[i-N];
}
}
ll segnodes = n-1;
node def;
s.assign(segnodes, def);
for(ll i = 1; i < segnodes; i++)
{
if((i-1)%2 == 0)
{
s[(i-1)/2].left = i;
}
else
{
s[(i-1)/2].right = i;
}
}
for(ll i = 0; i < M; i++)
{
s[i+N].on = A[i];
s[i+N].off = 1-s[i+N].on;
}
for(ll i = N-1; i >= 0; i--)
{
ll l = s[i].left;
ll r = s[i].right;
s[i].on = (2*s[l].on*s[r].on)%MOD;
s[i].on += (s[l].on*s[r].off)%MOD;
s[i].on %= MOD;
s[i].on += (s[l].off*s[r].off)%MOD;
s[i].on %= MOD;
s[i].off = (2*s[l].off*s[r].off)%MOD;
s[i].off += (s[l].on*s[r].off)%MOD;
s[i].off %= MOD;
s[i].off += (s[l].off*s[r].off)%MOD;
s[i].off %= MOD;
}
}
int count_ways(int L, int R)
{
if(subFirst)
{
for(ll i = L; i <= R; i++)
{
a[i] = 1-a[i];
}
return dfsSubFirst(0).first;
}
ll segnodes = s.size();
ll M = (segnodes+1)/2;
apply(0, L+1-M, R+1-M, 0, M-1);
return s[0].on;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
7096 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
7096 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
