Submission #627313

#	Time	Username	Problem	Language	Result	Execution time	Memory
627313		haojiandan	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1020 ms	20512 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=(1e9)+2022;
const int maxn=(2e5)+10;
vector<int> son[maxn];
int prod[maxn],n,m;
void dfs1(int u) {
	prod[u]=1;
	if ((int)son[u].size()==0) return;
	prod[u]=(int)son[u].size();
	for (int &v : son[u]) dfs1(v),prod[u]=(ll)prod[u]*prod[v]%mod;
}
int sum[maxn];
int pre[maxn],suf[maxn];
void dfs2(int u) {
	int sz=(int)son[u].size();
	for (int i=0;i<sz;i++) pre[i]=(ll)(i==0?1:pre[i-1])*prod[son[u][i]]%mod;
	for (int i=sz-1;i>=0;i--) suf[i]=(ll)(i==sz-1?1:suf[i+1])*prod[son[u][i]]%mod;
	for (int i=0;i<sz;i++) {
		int v=son[u][i];
		sum[v]=sum[u];
		if (i) sum[v]=(ll)sum[v]*pre[i-1]%mod;
		if (i<sz-1) sum[v]=(ll)sum[v]*suf[i+1]%mod;
	}
	for (int &v : son[u]) {
		dfs2(v);
	}
}
int flip[maxn*4];
int tr[maxn*4][2],col[maxn];
void pushup(int root) {
	tr[root][0]=(tr[root<<1][0]+tr[root<<1|1][0])%mod;
	tr[root][1]=(tr[root<<1][1]+tr[root<<1|1][1])%mod;
}
void build(int l,int r,int root) {
	if (l==r) {
		tr[root][0]=(col[l]?sum[l+n]:0);
		tr[root][1]=(col[l]?0:sum[l+n]);
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,root<<1),build(mid+1,r,root<<1|1);
	pushup(root);
}
void init(int _n, int _m, vector<int> P, vector<int> A) {
	n=_n,m=_m;
	for (int i=1;i<n+m;i++) son[P[i]].push_back(i);
	dfs1(0);
	sum[0]=1;
	dfs2(0);
	for (int i=0;i<m;i++) col[i]=A[i];
	build(0,m-1,1);
}
void puttag(int root) {
	flip[root]^=1,swap(tr[root][0],tr[root][1]);
}
void pushdown(int root) {
	if (flip[root]) puttag(root<<1),puttag(root<<1|1),flip[root]=0;
}
void add(int L,int R,int l,int r,int root) {
	if (L<=l&&r<=R) { puttag(root); return; }
	int mid=(l+r)>>1; pushdown(root);
	if (L<=mid) add(L,R,l,mid,root<<1);
	if (mid<R) add(L,R,mid+1,r,root<<1|1);
	pushup(root);
}
int count_ways(int l, int r) {
	l-=n,r-=n;
	add(l,r,0,m-1,1);
	return tr[1][0];
}

• 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