Submission #776575

#	Time	Username	Problem	Language	Result	Execution time	Memory
776575		SanguineChameleon	Digital Circuit (IOI22_circuit)	C++17	46 / 100	3055 ms	5604 KiB

circuit

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

const long long mod = 1e9 + 2022;
const int maxN = 1e5 + 20;
long long cont[maxN * 2];
long long ways[maxN * 2];
vector<int> ch[maxN];
int A[maxN];
int N, M;

void dfs1(int u) {
	if (ch[u].empty()) {
		ways[u] = 1;
		return;
	}
	ways[u] = (int)ch[u].size();
	for (auto v: ch[u]) {
		dfs1(v);
		ways[u] = ways[u] * ways[v] % mod;
	}
}

void dfs2(int u) {
	if (ch[u].empty()) {
		return;
	}
	int sz = ch[u].size();
	vector<long long> pref(sz);
	vector<long long> suf(sz);
	pref[0] = ways[ch[u][0]];
	for (int i = 1; i < sz; i++) {
		pref[i] = pref[i - 1] * ways[ch[u][i]] % mod;
	}
	suf[sz - 1] = ways[ch[u][sz - 1]];
	for (int i = sz - 2; i >= 0; i--) {
		suf[i] = suf[i + 1] * ways[ch[u][i]] % mod;
	}
	for (int i = 0; i < sz; i++) {
		cont[ch[u][i]] = cont[u] * (i > 0 ? pref[i - 1] : 1) % mod * (i < sz - 1 ? suf[i + 1] : 1) % mod;
		dfs2(ch[u][i]);
	}
}

void init(int _N, int _M, vector<int> P, vector<int> _A) {
	N = _N;
	M = _M;
	for (int i = 2; i <= N + M; i++) {
		ch[P[i - 1] + 1].push_back(i);
	}
	for (int i = 1; i <= M; i++) {
		A[i] = _A[i - 1];
	}
	dfs1(1);
	cont[1] = 1;
	dfs2(1);
}

int count_ways(int L, int R) {
	L -= N - 1;
	R -= N - 1;
	for (int i = L; i <= R; i++) {
		A[i] ^= 1;
	}
	long long res = 0;
	for (int i = 1; i <= M; i++) {
		if (A[i]) {
			res += cont[i + N];
			res %= mod;
		}
	}
	return res;
}

• 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: 28 / 28
• Subtask 8: 0 / 11