Submission #1061989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061989		jamjanek	Digital Circuit (IOI22_circuit)	C++17	100 / 100	782 ms	31200 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1'000'002'022;
long long pot2[200010];
long long iloL[200010], iloR[200010], ilo[200010];
vector<int>graf[200010];
long long policz(int n){
	return pot2[n-1];
}
long long wsp[200010];

void dfs1(int x){
	ilo[x] = 1;
	if(graf[x].size())
		ilo[x] = graf[x].size();
	for(auto j: graf[x]){
		dfs1(j);
		ilo[x] = ilo[j]*ilo[x]%mod;
	}
	long long pom = 1;
	for(int i=0;i<(int)graf[x].size();i++){
		pom = pom*ilo[graf[x][i]]%mod;
		iloL[graf[x][i]] = pom;
	}
	pom = 1;
	for(int i=(int)graf[x].size()-1;i>=0;i--){
		pom = pom*ilo[graf[x][i]]%mod;
		iloR[graf[x][i]] = pom;
	}
}

void dfs(int x, long long ilo){
	if(graf[x].size()==0){
		wsp[x] = ilo;
	}
	for(int i=0;i<(int)graf[x].size();i++){
		long long pom = ilo;
		if(i!=0)
			pom = (pom*iloL[graf[x][i-1]])%mod;
		if(i!=(int)graf[x].size()-1)
			pom = (pom*iloR[graf[x][i+1]])%mod;
		dfs(graf[x][i], pom);
	}
}
struct node{long long val1, val2;bool czy;};
const int base = 1<<17;
node tree[2*base];
int M, N;
void change(int w, int l, int p, int a, int b){
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		swap(tree[w].val1, tree[w].val2);
		tree[w].czy^=1;
		return;
	}
	if(tree[w].czy){
		swap(tree[w*2].val1, tree[w*2].val2);
		swap(tree[w*2+1].val1, tree[w*2+1].val2);
		tree[w*2].czy^=1;
		tree[w*2+1].czy^=1;
		tree[w].czy = 0;
	}
	change(w*2, l, (l+p)/2, a, b);
	change(w*2+1, (l+p)/2+1, p, a, b);
	tree[w].val1 = tree[w*2].val1+tree[w*2+1].val1;
	tree[w].val2 = tree[w*2].val2+tree[w*2+1].val2;
}

void init(int n, int m, std::vector<int> P, std::vector<int> A) {
	M = m;
	N = n;
	int i;
	pot2[0] = 1;
	for(int i=1;i<=n+m;i++)pot2[i] = pot2[i-1]*2%mod;
	
	for(int i=1;i<n+m;i++)
		graf[P[i]].push_back(i);
	wsp[0] = 1;
	dfs1(0);
	dfs(0, 1);
//	for(i=0;i<m;i++)
//		printf("%lld ", wsp[i+n]);printf("\n");
//	for(i=0;i<m+n;i++)
//		printf("%lld ", ilo[i]);printf("\n");
	for(int i=0;i<m;i++){
		tree[i+base].val1 = wsp[i+n]*A[i];
		tree[i+base].val2 = wsp[i+n]*(A[i]^1);
	}
	for(int i=base-1;i>0;i--){
		tree[i].val1 = (tree[i*2].val1+tree[i*2+1].val1)%mod;
		tree[i].val2 = (tree[i*2].val2+tree[i*2+1].val2)%mod;
	}
//	for(int i=0;i<M;i++)
//		printf("%lld ", tree[i+base].val1);printf("\n");
}

int count_ways(int L, int R) {
	change(1, 0, base-1, L-N, R-N);
	return tree[1].val1%mod;
}

Compilation message (stderr)

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:73:6: warning: unused variable 'i' [-Wunused-variable]
   73 |  int i;
      |      ^

• 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