Submission #631650

#	Time	Username	Problem	Language	Result	Execution time	Memory
631650		JustInCase	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3069 ms	4668 KiB

circuit

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <random>
#include <cstdlib>

#define debug(x) std::cout << #x << " " << (x) << '\n';
#define pb push_back
#define mp std::make_pair
#define remax(a, b) a = std::max((a), (b));
#define remin(a, b) a = std::min((a), (b));

#define countWays count_ways

const int32_t MOD = 1000002022;

struct Gate {
	int32_t value;
	int32_t waysOn, waysOff;
	std::vector<Gate*> children;
};

int32_t n, m;
std::vector<Gate> gates;

void init(int32_t _n, int32_t _m, std::vector<int32_t> p, std::vector<int32_t> a) {
	n = _n;
	m = _m;

	gates.resize(n + m);	

	for(int32_t i = 1; i < n + m; i++) {
		gates[p[i]].children.pb(&gates[i]);
		if(i >= n) {
			gates[i].value = a[i - n];
		}
	}
}

void computeDp() {
	for(int32_t i = n; i < n + m; i++) {
		gates[i].waysOn = (gates[i].value == 1);
		gates[i].waysOff = (gates[i].value == 0);
	}

	for(int32_t i = n - 1; i >= 0; i--) {
		gates[i].waysOn = 0;
		gates[i].waysOff = 0;

		int32_t k = gates[i].children.size();
		std::vector<std::vector<int32_t>> dp(k + 1, std::vector<int32_t>(k + 1));

		dp[0][0] = 1;
		for(int32_t pref = 1; pref <= k; pref++) {
			for(int32_t taken = 0; taken <= pref; taken++) {
				if(taken < pref) {
					int32_t waysNotTaken = ((int64_t) dp[pref - 1][taken] * gates[i].children[pref - 1]->waysOff) % MOD;
					dp[pref][taken] = ((int64_t) dp[pref][taken] + waysNotTaken) % MOD;
				}
				if(taken != 0) {
					int32_t waysTaken = ((int64_t) dp[pref - 1][taken - 1] * gates[i].children[pref - 1]->waysOn) % MOD;
					dp[pref][taken] = ((int64_t) dp[pref][taken] + waysTaken) % MOD;
				}
			}
		}

		//std::cout << i << ": ";
		for(int32_t j = 0; j <= k; j++) {
		//	std::cout << dp[k][j] << ", ";
			gates[i].waysOn = ((int64_t) gates[i].waysOn + (int64_t) dp[k][j] * j) % MOD;
			gates[i].waysOff = ((int64_t) gates[i].waysOff + (int64_t) dp[k][j] * (k - j)) % MOD;
		}
		//std::cout << "------>";

		//std::cout << gates[i].waysOn << ", " << gates[i].waysOff << '\n';
	}
}

int32_t countWays(int32_t l, int32_t r) {
	for(int32_t i = l; i <= r; i++) {
		gates[i].value = 1 - gates[i].value;
	}

	computeDp();

	return gates[0].waysOn;
}

• 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