Submission #1060281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060281		DorostWef	Digital Circuit (IOI22_circuit)	C++17	46 / 100	3056 ms	16464 KiB

circuit

#include "circuit.h"

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target ("avx2")

using namespace std;
#define int long long
const int N = 200023, M = 1000002022;
int a[N], p[N];
int ans[N];
int st[N];
vector <int> g[N];
int pre[N], suf[N];
int x[N];

void predfs (int v) {
	int sz = (int)g[v].size();
	if (sz == 0) {
		st[v] = 1;
		return;
	}
	st[v] = sz;
	for (int u : g[v]) {
		predfs (u);
		st[v] = (st[v] * st[u]) % M;
	}
}

void dfs (int v) {
	int sz = (int)g[v].size();
	if (sz == 0) {
		return;
	}
	pre[0] = 1;
	suf[sz] = 1;
	for (int i = 0; i < sz; i++) {
		int u = g[v][i];
		pre[i + 1] = (pre[i] * st[u]) % M;
	}
	for (int i = sz - 1; i >= 0; i--) {
		int u = g[v][i];
		suf[i] = (suf[i + 1] * st[u]) % M;
	}
	for (int i = 0; i < sz; i++) {
		int u = g[v][i];
		ans[u] = (ans[v] * ((pre[i] * suf[i + 1]) % M) % M);
	}
	for (int i = 0; i < sz; i++) {
		int u = g[v][i];
		dfs (u);
	}
}

int m, n;

void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
	n = N;
	for (int i = 0; i < N + M; i++) {
		g[P[i]].push_back(i);
	}
	m = M;
	for (int i = 0; i < M; i++)
		a[i] = A[i];
	predfs (0);
	ans[0] = 1;
	dfs (0);
	for (int i = 0; i < M; i++)
		p[i] = ans[i + N];
}

int32_t count_ways(int32_t L, int32_t R) {
	L -= n;
	R -= n;
	for (int i = L; i <= R; i++) {
		a[i] = 1 - a[i];
	}
	int sum = 0;
	for (int i = 0; i < m; i++) {
		sum += a[i] * p[i];
		sum %= M;
	}
	return (int32_t)sum;
}

• 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: 28 / 28
• Subtask 8: 0 / 11