Submission #837193

#	Time	Username	Problem	Language	Result	Execution time	Memory
837193		Sohsoh84	Digital Circuit (IOI22_circuit)	C++17	100 / 100	933 ms	62940 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MOD = 1000002022;
const ll MAXN = 1e6 + 10;

ll Z[MAXN], n, m, A[MAXN], CZ[MAXN], pw2;
vector<int> adj[MAXN];

namespace segment {
	ll sg[MAXN][2], lz[MAXN];

	void build(int l = 0, int r = m - 1, int v = 1) {
		if (l == r) sg[v][1 - A[l]] = Z[l];
		else {
			int mid = (l + r) >> 1;
			build(l, mid, v << 1);
			build(mid + 1, r, v << 1 | 1);

			sg[v][0] = (sg[v << 1][0] + sg[v << 1 | 1][0]) % MOD;
			sg[v][1] = (sg[v << 1][1] + sg[v << 1 | 1][1]) % MOD;
		}
	}

	void push(int v) {
		if (lz[v]) {
			swap(sg[v][0], sg[v][1]);
			if ((v << 1 | 1) < MAXN) lz[v << 1] ^= 1, lz[v << 1 | 1] ^= 1;
			lz[v] = 0;
		}
	}

	void update(int ql, int qr, int l = 0, int r = m - 1, int v = 1) {
		push(v);
		if (ql > r || qr < l) return;
		if (ql <= l && qr >= r) {
			lz[v] ^= 1;
			push(v);
			return;
		}

		int mid = (l + r) >> 1;
		update(ql, qr, l, mid, v << 1);
		update(ql, qr, mid + 1, r, v << 1 | 1);

		sg[v][0] = (sg[v << 1][0] + sg[v << 1 | 1][0]) % MOD;
		sg[v][1] = (sg[v << 1][1] + sg[v << 1 | 1][1]) % MOD;
	}
}

void dfs0(int v) {
	CZ[v] = (v < n ? adj[v].size() : 1);
	for (int u : adj[v]) {
		dfs0(u);
		CZ[v] = CZ[v] * CZ[u] % MOD;
	}
}

void dfs1(int v, ll z) {
	if (v >= n) {
		Z[v - n] = z;
		return;
	}

	int d = adj[v].size();
	vector<ll> pref_z(d + 2), suff_z(d + 2);
	pref_z[0] = 1;
	suff_z[d + 1] = 1;

	for (int i = 1; i <= d; i++)
		pref_z[i] = pref_z[i - 1] * CZ[adj[v][i - 1]] % MOD;

	for (int i = d; i > 0; i--)
		suff_z[i] = suff_z[i + 1] * CZ[adj[v][i - 1]] % MOD;

	for (int i = 1; i <= d; i++) {
		dfs1(adj[v][i - 1], z * pref_z[i - 1] % MOD * suff_z[i + 1] % MOD);	
	}
} 

void init(int N_, int M_, vector<int> P, vector<int> A_) {
	n = N_, m = M_;
	for (int i = 0; i < m; i++)
		A[i] = A_[i];

	for (int i = 1; i < n + m; i++)
		adj[P[i]].push_back(i);

	dfs0(0);
	dfs1(0, 1);
	segment::build();

	pw2 = 1;
	for (int i = 0; i < m; i++)
		pw2 = pw2 * 2 % MOD;

}

int count_ways(int L, int R) {
	L -= n, R -= n;
	segment::update(L, R);
	return segment::sg[1][0] % MOD;
}

• 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