제출 #1059700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1059700		AmirAli_H1	디지털 회로 (IOI22_circuit)	C++17	100 / 100	776 ms	32020 KiB

circuit

// In the name of Allah

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

typedef		long long			ll;
typedef		pair<int, int>		pii;
typedef		pair<ll, ll>		pll;

#define		endl				'\n'
#define		sep					' '
#define		F					first
#define		S					second
#define		Mp					make_pair
#define		pb					push_back
#define		all(x)				(x).begin(),(x).end()
#define		len(x)				((ll) (x).size())

const int maxn = (1 << 18) + 4;
const int mod = 1e9 + 2022;

struct node {
	int lazy; ll ans, ansx;
};

int n, m;
vector<int> adj[maxn]; int D[maxn];
ll valx[maxn], valr[maxn];
ll sm1[maxn], sm2[maxn];
ll val[maxn]; int A[maxn];
node t[maxn];

void pre_dfs(int v) {
	if (len(adj[v]) == 0) valx[v] = 1;
	else valx[v] = D[v];
	for (int u : adj[v]) {
		pre_dfs(u);
		valx[v] *= valx[u]; valx[v] %= mod;
	}
}

void res_dfs(int v) {
	for (int j = 0; j <= len(adj[v]); j++) {
		if (j == 0) sm1[j] = 1;
		else {
			int u = adj[v][j - 1];
			sm1[j] = sm1[j - 1] * valx[u] % mod;
		}
	}
	for (int j = 0; j <= len(adj[v]); j++) {
		if (j == 0) sm2[j] = 1;
		else {
			int u = adj[v][len(adj[v]) - j];
			sm2[j] = sm2[j - 1] * valx[u] % mod;
		}
	}
	
	val[v] = valr[v] * sm1[len(adj[v])] % mod;
	for (int j = 0; j < len(adj[v]); j++) {
		int u = adj[v][j];
		valr[u] = valr[v] * sm1[j] % mod * sm2[len(adj[v]) - j - 1] % mod;
	}
	for (int u : adj[v]) {
		res_dfs(u);
	}
}

node f(node a, node b, int lazy) {
	node res; res.lazy = 0;
	res.ans = (a.ans + b.ans) % mod;
	res.ansx = (a.ansx + b.ansx) % mod;
	if (lazy) {
		res.lazy ^= 1;
		swap(res.ans, res.ansx);
	}
	return res;
}

void build(int v, int tl, int tr) {
	t[v].lazy = 0;
	if (tr - tl == 1) {
		t[v].ans = val[tl]; t[v].ansx = 0;
		if (!A[tl]) swap(t[v].ans, t[v].ansx);
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v] = f(t[2 * v + 1], t[2 * v + 2], t[v].lazy);
}

void rev_val(int v, int tl, int tr, int l, int r) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	if (l == tl && r == tr) {
		t[v].lazy ^= 1;
		swap(t[v].ans, t[v].ansx);
		return ;
	}
	int mid = (tl + tr) / 2;
	rev_val(2 * v + 1, tl, mid, l, r); rev_val(2 * v + 2, mid, tr, l, r);
	t[v] = f(t[2 * v + 1], t[2 * v + 2], t[v].lazy);
}

void init(int N, int M, vector<int> Px, vector<int> Ax) {
	n = N; m = M;
	for (int i = 1; i < n + m; i++) {
		adj[Px[i]].pb(i); D[Px[i]]++;
	}
	pre_dfs(0);
	valr[0] = 1; res_dfs(0);
	
	for (int i = 0; i < m; i++) {
		val[i] = val[i + n]; A[i] = Ax[i];
	}
	build(0, 0, m);
}

int count_ways(int L, int R) {
	rev_val(0, 0, m, L - n, R - n + 1);
	return t[0].ans;
}

• 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