Submission #748839

#	Time	Username	Problem	Language	Result	Execution time	Memory
748839		QwertyPi	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3074 ms	8060 KiB

circuit

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

const int N_MAX = 2e5 + 11;
const int MOD = 1000002022;
vector<int> G[N_MAX];
int f[N_MAX], g[N_MAX];

void dfsU(int v){
	f[v] = G[v].empty() ? 1 : G[v].size();
	for(auto u : G[v]){
		dfsU(u);
		f[v] = (f[v] * f[u]) % MOD;
	}
}

int a[N_MAX << 2];
void upd(int pos, int val, int v, int l, int r){
	if(l == r) a[v] = val;
	else {
		int m = (l + r) / 2;
		if(pos <= m){
			upd(pos, val, v * 2 + 1, l, m);
		}else{
			upd(pos, val, v * 2 + 2, m + 1, r);
		}
		a[v] = a[v * 2 + 1] * a[v * 2 + 2] % MOD;
	}
}

int qry(int ql, int qr, int v, int l, int r){
	if(qr < l || r < ql) return 1;
	if(ql <= l && r <= qr) return a[v];
	int m = (l + r) / 2;
	
	int qx = qry(ql, qr, v * 2 + 1, l, m);
	int qy = qry(ql, qr, v * 2 + 2, m + 1, r);
	return qx * qy % MOD;
}

int qry_except(int x, int V){
	int qx = qry(0, x - 1, 0, 0, V - 1);
	int qy = qry(x + 1, V - 1, 0, 0, V - 1);
	return qx * qy % MOD;
}

void dfsD(int v){
	
	int V = G[v].size();
	for(int i = 0; i < V; i++){
		int u = G[v][i];
		upd(i, f[u], 0, 0, V - 1);
	}
	for(int i = 0; i < V; i++){
		int u = G[v][i];
		g[u] = g[v] * qry_except(i, V) % MOD;
	}
	for(int i = 0; i < V; i++){
		dfsD(G[v][i]);
	} 
}

int ac[N_MAX];
int N, M;
void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) {
	::N = N; ::M = M;
	for(int i = 1; i < N + M; i++){
		G[P[i]].push_back(i);
	}
	dfsU(0);
	g[0] = 1; dfsD(0);
	
	for(int i = N; i < N + M; i++){
		ac[i] = A[i - N];
	}
}

int32_t count_ways(int32_t L, int32_t R) {
	for(int i = L; i <= R; i++){
		ac[i] = !ac[i];
	}
	
	int ans = 0;
	for(int i = N; i < N + M; i++){
		ans += ac[i] * g[i];
		ans %= MOD;
	}
	return ans;
}

• 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