Submission #1245699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245699		Nelt	Digital Circuit (IOI22_circuit)	C++20	2 / 100	193 ms	9664 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"

using namespace std;
const ll N = 2e5 + 5, mod = 1e9 + 2022;
vector<ll> g[N];
ll a[N], n, m, sub[N], p[N], val[N];
ll st[2][N << 2], lazy[N << 2];
void init(ll v)
{
    sub[v] = max(1, (int)g[v].size());
    for (ll to : g[v])
        init(to), sub[v] = sub[v] * sub[to] % mod;
}
void dfs(ll v)
{
    ll pref[g[v].size()], suf[g[v].size()];
    for (ll i = 0; i < g[v].size(); i++)
        pref[i] = (i == 0 ? 1 : pref[i - 1]) * sub[g[v][i]] % mod;
    for (ll i = (int)g[v].size() - 1; i >= 0; i--)
        suf[i] = (i + 1 < g[v].size() ? suf[i + 1] : 1) * sub[g[v][i]] % mod;
    for (ll i = 0; i < g[v].size(); i++)
        val[g[v][i]] = (i - 1 < 0 ? 1 : pref[i - 1]) * (i + 1 < g[v].size() ? suf[i + 1] : 1) % mod * val[v] % mod, dfs(g[v][i]);
}
void build(ll l, ll r, ll v)
{
    if (l == r)
    {
        st[a[l + n]][v] = val[l + n];
        return;
    }
    ll mid = (l + r) >> 1;
    build(l, mid, v << 1);
    build(mid + 1, r, v << 1 | 1);
    for (ll i = 0; i < 2; i++)
        st[i][v] = st[i][v << 1] + st[i][v << 1 | 1];
}
void push(ll v, ll l, ll r)
{
    if (l != r and lazy[v])
    {
        swap(st[0][v << 1], st[1][v << 1]);
        swap(st[0][v << 1 | 1], st[1][v << 1 | 1]);
        lazy[v << 1] ^= 1;
        lazy[v << 1 | 1] ^= 1;
        lazy[v] = 0;
    }
}
void modify(ll i, ll j, ll l, ll r, ll v)
{
    if (max(i, l) > min(j, r))
        return;
    push(v, l, r);
    if (i <= l and r <= j)
    {
        swap(st[0][v], st[1][v]);
        lazy[v] ^= 1;
        return;
    }
    ll mid = (l + r) >> 1;
    modify(i, j, l, mid, v << 1);
    modify(i, j, mid + 1, r, v << 1 | 1);
    for (ll i = 0; i < 2; i++)
        st[i][v] = st[i][v << 1] + st[i][v << 1 | 1];
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
    n = N, m = M;
    for (ll i = 1; i < n + m; i++)
        g[p[i] = P[i]].push_back(i);
    for (ll i = 0; i < m; i++)
        a[i + n] = A[i];
        init(0);
        val[0] = 1;
        dfs(0);
    build(0, m - 1, 1);
}

int count_ways(int l, int r)
{
    modify(l - n, r - n, 0, m - 1, 1);
    return st[1][1];
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11