제출 #776581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776581		SanguineChameleon	Digital Circuit (IOI22_circuit)	C++17	100 / 100	871 ms	38488 KiB

circuit

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

struct node {
	long long sum1 = 0;
	long long sum2 = 0;
	bool flip = false;
};

const long long mod = 1e9 + 2022;
const int maxN = 1e5 + 20;
long long cont[maxN * 2];
long long ways[maxN * 2];
node tree[maxN * 4];
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 flip(int id) {
	swap(tree[id].sum1, tree[id].sum2);
	tree[id].flip ^= 1;
}

void merge(int id) {
	tree[id].sum1 = (tree[id * 2].sum1 + tree[id * 2 + 1].sum1) % mod;
	tree[id].sum2 = (tree[id * 2].sum2 + tree[id * 2 + 1].sum2) % mod;
	tree[id].flip = false;
}

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id].sum1 = A[lt] ? cont[N + lt] : 0;
		tree[id].sum2 = !A[lt] ? cont[N + lt] : 0;
		tree[id].flip = false;
		return;
	}
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
	merge(id);
}

void update(int id, int lt, int rt, int ql, int qr) {
	if (lt == ql && rt == qr) {
		flip(id);
		return;
	}
	if (tree[id].flip) {
		flip(id * 2);
		flip(id * 2 + 1);
	}
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		update(id * 2, lt, mt, ql, qr);
	}
	else if (ql >= mt + 1) {
		update(id * 2 + 1, mt + 1, rt, ql, qr);
	}
	else {
		update(id * 2, lt, mt, ql, mt);
		update(id * 2 + 1, mt + 1, rt, mt + 1, qr);
	}
	merge(id);
}

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);
	build(1, 1, M);
}

int count_ways(int L, int R) {
	L -= N - 1;
	R -= N - 1;
	update(1, 1, M, L, R);
	return tree[1].sum1;
}

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