Submission #1059904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059904		parsadox2	Digital Circuit (IOI22_circuit)	C++17	46 / 100	3040 ms	7512 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"

using namespace std;

const int N = 2e5 + 10 , mod = 1000002022;
int sbt[N] , n , m , zarib[N];
vector <int> p , a , adj[N];

void Find_sbt(int v)
{
	sbt[v] = adj[v].size();
	if(sbt[v] == 0)
		sbt[v] = 1;
	for(auto u : adj[v])
	{
		Find_sbt(u);
		sbt[v] = 1LL * sbt[v] * sbt[u] % mod;
	}
}

void Add(int v , int val)
{
	if(v >= n)
	{
		zarib[v - n] = 1LL * zarib[v - n] * val % mod;
		return;
	}
	for(auto u : adj[v])
		Add(u , val);
}

void Dfs(int v)
{
	for(auto u : adj[v])  for(auto w : adj[v])  if(u != w)
		Add(w , sbt[u]);
	for(auto u : adj[v])
		Dfs(u);
}

void init(int nn , int mm , vector <int> pp , vector <int> aa)
{
	n = nn;
	m = mm;
	p = pp;
	a = aa;
	for(int i = 0 ; i < m ; i++)
		zarib[i] = 1;
	for(int i = 1 ; i < n + m ; i++)
		adj[p[i]].push_back(i);
	Find_sbt(0);
	Dfs(0);
	/*for(int i = 0 ; i < m ; i++)
		cout << a[i] << " " << zarib[i] << endl;
		*/
}

int count_ways(int l , int r)
{
	for(int i = l ; i <= r ; i++)
		a[i - n] ^= 1;
	int res = 0;
	for(int i = 0 ; i < m ; i++)  if(a[i] == 1)
	{
		res = (res + zarib[i]) % mod;
	}
	return res;
}

• 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