Submission #1170780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170780		thelegendary08	Digital Circuit (IOI22_circuit)	C++17	0 / 100	226 ms	15092 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define f0r(i,n) for(int i = 0;  i< n; i++)
#define mp make_pair
using namespace std;
vector<signed> par;
vector<signed> v;
vector<vi> adj;
int n,m;
const int mod = 1e9 + 2022;
const int mxn = 2e5 + 5;
vector<vi>dp(mxn, vi(2));
void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
	n = N; m = M; par = P; v = A;
	adj.resize(n + m);
	FOR(i, 1, n+m){
		adj[P[i]].pb(i);
	}
	FOR(i, n, n + m){
		if(v[i-n] == 1){
			dp[i][1] = 1;
		}
		else dp[i][0] = 1;
	}
	for(int i = n - 1; i>=0; i--){
		int a = adj[i][0];
		int b = adj[i][1];
		dp[i][1] = dp[a][1] * dp[b][1] % mod * 2 % mod + dp[a][1] * dp[b][0] % mod + dp[b][1] * dp[a][0] % mod;
		dp[i][1] %= mod;
		dp[i][0] = dp[a][1] * dp[b][0] % mod + dp[b][1] * dp[a][0] % mod + dp[a][0] * dp[b][0] % mod * 2 % mod;
		dp[i][0] %= mod;
	}
}

signed count_ways(signed l, signed r) {
	v[l-n] = 1 - v[l-n];
	if(v[l-n] == 1)dp[l][1] = 1;
	else dp[l][0] = 0;
	int cur = l;
	while(cur != 0){
		cur = par[cur];
		int a = adj[cur][0];
		int b = adj[cur][1];
		dp[cur][1] = dp[a][1] * dp[b][1] % mod * 2 % mod + dp[a][1] * dp[b][0] % mod + dp[b][1] * dp[a][0] % mod;
		dp[cur][1] %= mod;
		dp[cur][0] = dp[a][1] * dp[b][0] % mod + dp[b][1] * dp[a][0] % mod + dp[a][0] * dp[b][0] % mod * 2 % mod;
		dp[cur][0] %= mod;
	}
	
	return dp[0][1];
}

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