Submission #835010

#	Time	Username	Problem	Language	Result	Execution time	Memory
835010		pavement	Digital Circuit (IOI22_circuit)	C++17	7 / 100	3080 ms	4108 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];
		}
		int ret = 0;
		for (int bm = 0; bm < (1 << (int)adj[u].size()); bm++) {
			int cur = __builtin_popcount(bm);
			for (int i = 0; i < (int)adj[u].size(); i++) {
				int tmp = (bm & (1 << i) ? dp(adj[u][i]) : tot(adj[u][i]) - dp(adj[u][i])) % MOD;
				if (tmp < 0) {
					tmp += MOD;
				}
				cur = (ll)cur * (ll)tmp % MOD;
			}
			ret = (ret + cur) % MOD;
		}
		return dp_mem[u] = ret;
	};
	
	return dp(0);
}

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