Submission #1245714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245714		Nelt	Digital Circuit (IOI22_circuit)	C++20	18 / 100	3050 ms	7412 KiB

circuit

#include "circuit.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"

using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 2022;
vector<int> g[N];
int a[N], n, m, dp[N], sub[N], p[N];
void dfs(int v)
{
    if (!g[v].size())
    {
        dp[v] = a[v];
        sub[v] = 1;
        return;
    }
    sub[v] = g[v].size();
    dp[v] = 0;
    int cur = 1;
    for (int to : g[v])
    {
        dfs(to);
        sub[v] = 1ll * sub[v] * sub[to] % mod;
        dp[v] = (1ll * dp[v] * sub[to] + 1ll * cur * dp[to]) % mod;
        cur = 1ll * cur * sub[to] % mod;
    }
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
    n = N, m = M;
    for (int i = 1; i < n + m; i++) g[p[i] = P[i]].push_back(i);
    for (int i = 0; i < m; i++) a[i + n] = A[i];
}

int count_ways(int l, int r)
{
    for (int 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