Submission #835020

#	Time	Username	Problem	Language	Result	Execution time	Memory
835020		pavement	Digital Circuit (IOI22_circuit)	C++17	22 / 100	3091 ms	8784 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

using ll = long long;

const int MOD = (int)1e9 + 2022;
int N, M;
vector<int> A, P, tot_mem, dp_mem;
vector<vector<int> > adj;

int tot(int u) {
	if (tot_mem[u] != -1) {
		return tot_mem[u];
	}
	if (u >= N) {
		return tot_mem[u] = 1;
	}
	int ret = (int)(adj[u].size());
	for (auto v : adj[u]) {
		ret = ((ll)ret * (ll)tot(v)) % MOD;
	}
	return tot_mem[u] = ret;
}

int dp(int u) {
	if (dp_mem[u] != -1) {
		return dp_mem[u];
	}
	if (u >= N) {
		return dp_mem[u] = A[u - N];
	}
	vector<int> sub_dp((int)adj[u].size() + 1, 0);
	sub_dp[0] = 1;
	for (auto v : adj[u]) {
		vector<int> new_sub_dp((int)adj[u].size() + 1);
		for (int i = 0; i <= (int)adj[u].size(); i++) {
			new_sub_dp[i] = ((i ? (ll)sub_dp[i - 1] * dp(v) : 0ll) % MOD + (ll)sub_dp[i] * ((ll)tot(v) - dp(v)) % MOD) % MOD;
			if (new_sub_dp[i] < 0) {
				new_sub_dp[i] += MOD;
			}
		}
		sub_dp = new_sub_dp;
	}
	int ret = 0;
	for (int i = 0; i <= (int)adj[u].size(); i++) {
		ret = (ret + (ll)i * sub_dp[i] % MOD) % MOD;
	}
	return dp_mem[u] = ret;
}

void init(int N, int M, vector<int> P, vector<int> A) {
	::N = N;
	::M = M;
	::P = P;
	::A = A;
	adj.resize(N + M);
	tot_mem = dp_mem = vector<int>(N + M, -1);
	for (int i = 1; i < N + M; i++) {
		adj[P[i]].pb(i);
	}
}

int count_ways(int L, int R) {
	for (int i = L - N; i <= R - N; i++) {
		A[i] = !A[i];
	}
	
	for (int i = L; i <= R; i++) {
		for (int u = i; u != -1 && dp_mem[u] != -1; u = P[u]) {
			dp_mem[u] = -1;
		}
	}
	
	return dp(0);
}

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