Submission #1057986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057986		fuad27	Digital Circuit (IOI22_circuit)	C++17	2 / 100	3041 ms	6108 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1'000'002'022; // ????? 
const int N = 1e5+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) {
	long long sumtot = 0;
	for(int to:child[at]) {
		sumtot+=total[to];
		sumtot%=mod;
	}
	int c = child[at].size();
	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]]);
	}
}
vector<int> A;
int nn;
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);
}

int count_ways(int L, int R) {
	L-=nn, R-=nn;
	for(int i = L;i<=R;i++)A[i]^=1;
	long long sum = 0;
	for(int i = 0;i<(int)A.size();i++) {
		sum=(sum+(1-A[i])*contrib[nn+i])%mod;
	}
	int ans = (total[0]-sum)%mod;
	return ans;
}

• Subtask 1: 2 / 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