Submission #1237368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237368		RakhimovAmir	Digital Circuit (IOI22_circuit)	C++20	22 / 100	3059 ms	15004 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022; 
vector<vector<int>> v;
vector<vector<ll>> d;
vector<int> A, pr;
int N, M;
void dfs(int x) {
	// cout << "ker: " << x << " " << v[x].size() << "\n";
	d[x][0] = d[x][1] = 0;
	if (x >= N) {
		d[x][A[x - N]] = 1;
		d[x][A[x - N] ^ 1] = 0;
		// cout << x << ": " << d[x][0] << " " << d[x][1] << "\n";
		return;
	}
	for (auto to : v[x])
		dfs(to);
	vector<int> last(v[x].size() + 1, 0), dp(v[x].size() + 1, 0);
	last[0] = 1;
	for (auto to : v[x]) {
		for (int j = 0; j < v[x].size() + 1; j++) {
			if (j) {
				dp[j] = last[j - 1] * d[to][1] % MOD;
			}
			dp[j] += last[j] * d[to][0] % MOD;
			dp[j] %= MOD;
		}
		last = dp;
		fill(dp.begin(), dp.end(), 0);
	}
	int suff = 0, pref = 0;
	for (int i = 0; i <= v[x].size(); i++) {
		pref += last[i];
		pref %= MOD;
		// cout << last[i] << " ";
	}
	// cout << "\n";
	for (int i = v[x].size(); i >= 1; i--) {
		pref -= last[i];
		pref %= MOD;
		if (pref < 0) {
			pref += MOD;
		}
		suff += last[i];
		suff %= MOD;
		d[x][1] += suff;
		d[x][1] %= MOD;
		d[x][0] += pref;
		d[x][0] %= MOD;
	}
	// dfs(pr[x]);
	// cout << x << ": " << d[x][0] << " " << d[x][1] << "\n";
}

void upd(int x) {
	d[x][0] = d[x][1] = 0;
	if (x >= N) {
		d[x][A[x - N]] = 1;
		d[x][A[x - N] ^ 1] = 0;
		// cout << x << ": " << d[x][0] << " " << d[x][1] << "\n";
		upd(pr[x]);
		return;
	}
	vector<int> last(v[x].size() + 1, 0), dp(v[x].size() + 1, 0);
	last[0] = 1;
	for (auto to : v[x]) {
		for (int j = 0; j < v[x].size() + 1; j++) {
			if (j) {
				dp[j] = last[j - 1] * d[to][1] % MOD;
			}
			dp[j] += last[j] * d[to][0] % MOD;
			dp[j] %= MOD;
		}
		last = dp;
		fill(dp.begin(), dp.end(), 0);
	}
	int suff = 0, pref = 0;
	for (int i = 0; i <= v[x].size(); i++) {
		pref += last[i];
		pref %= MOD;
		// cout << last[i] << " ";
	}
	// cout << "\n";
	for (int i = v[x].size(); i >= 1; i--) {
		pref -= last[i];
		pref %= MOD;
		if (pref < 0) {
			pref += MOD;
		}
		suff += last[i];
		suff %= MOD;
		d[x][1] += suff;
		d[x][1] %= MOD;
		d[x][0] += pref;
		d[x][0] %= MOD;
	}
	// cout << x << " " << d[x][0] << " " << d[x][1] << "\n";
	if (x)
		upd(pr[x]);
}

void init(int N, int M, vector<int> P, vector<int> A) {
	pr.resize(N + M);
	v.resize(N + M);
	d.resize(N + M);
	::A = A;
	::N = N;
	::M = M;
	for (int i = 1; i < N + M; i++) {
		v[P[i]].push_back(i);
		pr[i] = P[i];
		// cout << "add " << i << " " << v[i].size() << "\n";
	}
	for (int i = 0; i < N + M; i++) {
		d[i].resize(2);
	}
	dfs(0);
}

int count_ways(int L, int R) {
	for (int i = L; i <= R; i++) {
		A[i - N] ^= 1;
	}
	if (N <= 1000 && M <= 1000) {
		dfs(0);
		return d[0][1];
	}
	for (int i = L; i <= R; i++) {
		upd(i);
	}
	return d[0][1];
}

• 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