Submission #1058044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058044		fuad27	Digital Circuit (IOI22_circuit)	C++17	100 / 100	703 ms	37568 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1'000'002'022; // ????? 
const int N = 2e5+10;
vector<int> child[N];
long long total[N];
long long contrib[N];
 
void dfs(int at) {
	total[at] = max(1, (int)child[at].size());
	for(int to:child[at]) {
		dfs(to);
		total[at] = (total[at] * total[to])%mod;
	}
}
void dfs2(int at) {
	if(!child[at].size())return;
	long long sumtot = 0;
	for(int to:child[at]) {
		sumtot+=total[to];
		sumtot%=mod;
	}
	int c = child[at].size();
	vector<long long> pref(c);
	pref[0] = 1;
	for(int i = 1;i<c;i++) {
		pref[i] = (pref[i-1] * total[child[at][i-1]])%mod;
	}
	long long suff = 1;
	for(int i = c-1;i>=0;i--) {
		contrib[child[at][i]] = (((suff*pref[i])%mod)*contrib[at])%mod;
		dfs2(child[at][i]);
		suff = (suff*total[child[at][i]])%mod;
	}
}
vector<int> A;
int nn;

pair<long long, long long> T[4*N];
int lz[4*N];
void build(vector<int> &a, int tl = 0, int tr = N-1, int v = 1) {
	if(tl == tr) {
		if((int)a.size() > tl)T[v] = {a[tl], 0};
		else T[v] = {0, 0};
		return;
	}
	int tm = (tl+tr)/2;
	build(a, tl, tm, 2*v);
	build(a, tm+1, tr, 2*v+1);
	T[v].first = (T[2*v].first + T[2*v+1].first)%mod;
	T[v].second = (T[2*v].second + T[2*v+1].second)%mod;
}
void push(int v) {
	if(lz[v]) {
		lz[v] = 0;
		lz[2*v]^=1;
		lz[2*v+1]^=1;
		swap(T[2*v].first, T[2*v].second);
		swap(T[2*v+1].first, T[2*v+1].second);
	}
}
void update(int l, int r, int tl = 0, int tr = N-1, int v = 1) {
	if(r < tl or tr < l)return;
	if(l<=tl and tr<=r) {
		lz[v] ^= 1;
		swap(T[v].first, T[v].second);
		return;
	}
	push(v);
	int tm = (tl+tr)/2;
	update(l, r, tl, tm, 2*v);
	update(l, r, tm+1, tr, 2*v+1);
	T[v].first = (T[2*v].first + T[2*v+1].first)%mod;
	T[v].second = (T[2*v].second + T[2*v+1].second)%mod;
}

void init(int n, int m, std::vector<int> p, std::vector<int> a) {
	nn=n;
	A = a;
	for(int i = 1;i<m+n;i++) {
		child[p[i]].push_back(i);
	}
	for(int i= 0;i<m+n;i++)contrib[i] = 1;
	dfs(0);
	dfs2(0);
	vector<int> cont(m);
	for(int i = 0;i<m;i++) {
		cont[i] = contrib[i+n];
	}
	build(cont);
	for(int i = 0;i<m;i++) {
		if(A[i]) {
			update(i, i);
		}
	}
}
 
int count_ways(int L, int R) {
	L-=nn, R-=nn;
	update(L, R);
	long long ans = (total[0] - T[1].first)%mod;
	ans+=mod;
	ans%=mod;
	return ans;
}

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