Submission #835014

#	Time	Username	Problem	Language	Result	Execution time	Memory
835014		pavement	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3071 ms	4148 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;
vector<vector<int> > adj;

void init(int N, int M, vector<int> P, vector<int> A) {
	::N = N;
	::M = M;
	::A = A;
	adj.resize(N + M);
	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];
	}
	
	vector<int> tot_mem(N + M, -1), dp_mem(N + M, -1);
	
	function<int(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;
	};
	
	function<int(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;
	};
	
	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