Submission #1187721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187721		ByeWorld	Digital Circuit (IOI22_circuit)	C++20	18 / 100	3039 ms	10788 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf ((id<<1))
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 3e5+10;
const ll MOD = 1e9+2022;
ll sum(ll a, ll b){ return (a+b)%MOD;}
ll sub(ll a, ll b){ return (a+MOD-b)%MOD;}
void chsum(ll &a, ll b){ a = (a+b)%MOD;}
ll mul(ll a, ll b){ return (a*b)%MOD; }
void chmul(ll &a, ll b){ a = (a*b)%MOD;}
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }

int n, m, par[MAXN], a[MAXN];
ll dp[MAXN][3], on[MAXN];
vector<int> adj[MAXN];

void dfs(int nw){
	if(adj[nw].empty()){
		dp[nw][0] = dp[nw][1] = 0;
		dp[nw][a[nw]] = 1;
		return;
	}
	for(auto nx : adj[nw]) dfs(nx);
	int siz = adj[nw].size();

	for(int i=0; i<=siz+1; i++) on[i] = 0;
	on[0] = 1;
	for(auto nx : adj[nw]){
		for(int i=siz; i>=0; i--){
			on[i] = mul(on[i], dp[nx][0]);
			if(i>=1) 
				chsum(on[i], mul(on[i-1], dp[nx][1]) );
		}
	}
	for(int i=siz; i>=0; i--) chsum(on[i], on[i+1]); // suffix
	dp[nw][1] = dp[nw][0] = 0;

	for(int i=1; i<=siz; i++) chsum(dp[nw][1], on[i]); //i...siz
	for(int i=1; i<=siz; i++) chsum(dp[nw][0], sub(on[0], on[i])); //0..i-1
}

void init(int N, int M, std::vector<int> P, std::vector<int> AA) {
	n = N; m = M;
	for(int i=1; i<=n+m; i++){
		par[i] = P[i-1]+1;
		adj[par[i]].pb(i);
	}
	for(int i=1; i<=m; i++){
		a[i+n] = AA[i-1];
	}
}

int count_ways(int L, int R) {
	int l = L+1, r = R+1;
	for(int i=l; i<=r; i++) a[i] = 1-a[i];
	dfs(1);
	
	// for(int i=1; i<=3; i++){
	// 	cout << dp[i][0] << ' ' << dp[i][1] << " xx\n";
	// }
	return (int)dp[1][1];
}

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