Submission #680910

#	Time	Username	Problem	Language	Result	Execution time	Memory
680910		Justin1	Digital Circuit (IOI22_circuit)	C++17	0 / 100	636 ms	7704 KiB

circuit

//0 - n-1 = non leaf, n - m-1 = leaf

#include "circuit.h"
#include <bits/stdc++.h>
// #define signed int
#define int long long
using namespace std;

const int mod = 1e9 + 2022;
int n, m, k, x, y, z;
int dp[200005][2];
vector<signed> par, gph[200005];

void dfs(int id) {
	int L = -1, R = -1;
	if (gph[id].size()) L = gph[id][0], R = gph[id][1];
	else return;
	dfs(L), dfs(R);
	dp[id][0] = dp[L][1] * dp[R][0] + dp[L][0] * dp[R][1] + 2 * dp[L][0] * dp[R][0];
	dp[id][1] = dp[L][1] * dp[R][0] + dp[L][0] * dp[R][1] + 2 * dp[L][1] * dp[R][1];
	dp[id][0] %= mod;
	dp[id][1] %= mod;
}

void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
	n = N, m = M, par = P;
	for (int i = 1; i < n + m; i++) gph[P[i]].push_back(i);
	for (int i = n; i < m; i++) dp[i][A[i-n]] = 1;
	dfs(0);
}

signed count_ways(signed L, signed R) {
	swap(dp[L][0], dp[R][1]);
	int id = par[L];
	while (id != -1) {
		int L = gph[id][0], R = gph[id][1];
		dp[id][0] = dp[L][1] * dp[R][0] + dp[L][0] * dp[R][1] + 2 * dp[L][0] * dp[R][0];
		dp[id][1] = dp[L][1] * dp[R][0] + dp[L][0] * dp[R][1] + 2 * dp[L][1] * dp[R][1];
		dp[id][0] %= mod;
		dp[id][1] %= mod;
		id = par[id];
	}
	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