Submission #1245681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245681		Nelt	Digital Circuit (IOI22_circuit)	C++20	18 / 100	3086 ms	8264 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, dp[N], sub[N], p[N];
void dfs(ll v)
{
    if (!g[v].size())
    {
        dp[v] = a[v];
        sub[v] = 1;
        return;
    }
    sub[v] = g[v].size();
    for (ll to : g[v])
    {
        dfs(to);
        sub[v] = sub[v] * sub[to] % mod;
    }
    ll deg = g[v].size();
    ll dp1[deg + 1], ndp[deg + 1];
    for (ll i = 0; i <= deg; i++)
        dp1[i] = 0;
    dp1[0] = 1;
    for (ll to : g[v])
    {
        for (ll x = 0; x <= deg; x++)
            ndp[x] = dp1[x] * (sub[to] - dp[to] + mod) % mod;
        for (ll x = 0; x < deg; x++)
            ndp[x + 1] = (ndp[x + 1] + dp1[x] * dp[to] % mod) % mod;
        for (ll x = 0; x <= deg; x++) 
            dp1[x] = ndp[x];
    }
    dp[v] = 0;
    for (ll i = 0; i <= deg; i++) dp[v] = (dp[v] + dp1[i] * i) % mod;
}
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];
}

int count_ways(int l, int r)
{
    for (ll i = l; i <= r; i++) a[i] ^= 1;
    dfs(0);
    return dp[0];
}

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