Submission #666992

#	Time	Username	Problem	Language	Result	Execution time	Memory
666992		mychecksedad	Digital Circuit (IOI22_circuit)	C++17	18 / 100	19 ms	2820 KiB

circuit

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 2e3 + 10, MOD = 1000002022;

int n, m;
ll ans[N][2];
vector<ll> dp[N];
vector<int> source, g[N];
void calculate(int v, int u){
	int s = g[v].size(); 
	v ? s-- : 1;
	vector<ll> temp(s + 2, 0);

	for(int i = 0; i <= s; ++i){
		if(i > 0)
			(temp[i] += dp[v][i - 1] * ans[u][1]) %= MOD;
		(temp[i] += dp[v][i] * ans[u][0]) %= MOD;
	}

	dp[v] = temp;
}

void dfs(int v, int p){
	if(v >= n){
		ans[v][source[v - n]] = 1;
		ans[v][source[v - n] ^ 1] = 0;
		return;
	}
	int s = g[v].size();
	v ? s-- : 1;
	dp[v].clear();
	dp[v].resize(s + 2, 0);
	dp[v][0] = 1;
	for(int u: g[v]){
		if(u != p){
			dfs(u, v);
			calculate(v, u);
		}
	}
	ans[v][0] = ans[v][1] = 0;
	for(ll i = 0; i <= s; ++i){
		(ans[v][0] += dp[v][i] * (s - i)) %= MOD;
		(ans[v][1] += dp[v][i] * i) %= MOD;
	}
}

void init(int N, int M, vector<int> P, vector<int> A){
	source = A;
	n = N;
	m = M;
	for(int i = 1; i < n + m; ++i){
		g[i].pb(P[i]);
		g[P[i]].pb(i);
	}
}


int count_ways(int L, int R){
	L -= n, R -= n;
	for(int i = L; i <= R; ++i) source[i] ^= 1;
	dfs(0, 0);
	return ans[0][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