Submission #988456

#	Time	Username	Problem	Language	Result	Execution time	Memory
988456		siewjh	Digital Circuit (IOI22_circuit)	C++17	100 / 100	894 ms	40876 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
const ll mod = 1'000'002'022;
vector<int> adj[MAXN];
ll sbt[MAXN], lv[MAXN]; bool st[MAXN];
struct node{
	int s, e, m; ll v0, v1; bool lazy;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1, v0 = 0, v1 = 0, lazy = 0;
		if (s == e) (st[s] ? v1 : v0) = lv[s];
		else{
			l = new node(s, m); r = new node(m + 1, e);
			v0 = l->v0 + r->v0; v1 = l->v1 + r->v1;
		}
	}
	void push(){
		swap(v0, v1); lazy = !lazy;
	}
	void propo(){
		if (s == e) return;
		if (lazy){
			l->push(); r->push();
			lazy = 0;
		}
	}
	void update(int x, int y){
		if (x == s && y == e){
			push(); return;
		}
		propo();
		if (y <= m) l->update(x, y);
		else if (x > m) r->update(x, y);
		else{
			l->update(x, m); r->update(m + 1, y);
		}
		propo();
		v0 = l->v0 + r->v0; v1 = l->v1 + r->v1;
	}
} *root;
void dfs(int x){
	sbt[x] = max(1, (int)(adj[x].size()));
	for (auto nn : adj[x]){
		dfs(nn); sbt[x] = sbt[x] * sbt[nn] % mod;
	}
}
void dfs2(int x, ll uv){
	int asz = adj[x].size();
	vector<ll> lp(asz + 2), rp(asz + 2);
	lp[0] = 1; rp[asz + 1] = 1;
	for (int i = 1; i <= asz; i++) lp[i] = lp[i - 1] * sbt[adj[x][i - 1]] % mod;
	for (int i = asz; i >= 1; i--) rp[i] = rp[i + 1] * sbt[adj[x][i - 1]] % mod;
	for (int i = 1; i <= asz; i++){
		int nn = adj[x][i - 1]; dfs2(nn, uv * lp[i - 1] % mod * rp[i + 1] % mod);
	}
	lv[x] = uv;
}
void init(int N, int M, vector<int> P, vector<int> A) {
	int tot = N + M;
	for (int i = 1; i < tot; i++) adj[P[i]].push_back(i);
	for (int i = N; i < tot; i++) st[i] = A[i - N];
	dfs(0); dfs2(0, 1);
	root = new node(N, tot - 1);
}
int count_ways(int L, int R) {
	root->update(L, R);
	return root->v1 % 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