Submission #780360

#	Time	Username	Problem	Language	Result	Execution time	Memory
780360		mousebeaver	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3090 ms	4152 KiB

circuit

#define ll long long
#define pll pair<ll, ll>
#define MOD 1000002022
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

ll n = 0;
vector<ll> a(0);
vector<vector<ll>> adjlist(0);

void init(int N, int M, std::vector<int> P, std::vector<int> A) 
{
    n = N+M;
    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];
    }
}

pll dfs(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 = dfs(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};
}

int count_ways(int L, int R) 
{
    for(ll i = L; i <= R; i++)
    {
        a[i] = 1-a[i];
    }
    return dfs(0).first;
}

• 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