Submission #1077296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077296		Muhammad_Aneeq	Digital Circuit (IOI22_circuit)	C++17	7 / 100	3036 ms	7888 KiB

circuit

#include <vector>
using namespace std;
int const MAXN=2e5+10,mod=1e9+2022;
vector<int>nei[MAXN]={};
long long comp[2][MAXN]={};
int p[MAXN]={};
bool state[MAXN]={};
void calc(int x)
{
	vector<int>z=nei[x];
	comp[0][x]=comp[1][x]=0;
	for (int i=0;i<(1<<z.size());i++)
	{
		int cnt=0;
		long long pro=1;
		for (int j=0;j<z.size();j++)
		{
			if ((1<<j)&i)
			{
				cnt++;
				pro=(pro*comp[1][z[j]])%mod;
			}
			else
				pro=(pro*comp[0][z[j]])%mod;
		}
		comp[1][x]+=cnt*pro;
		comp[0][x]+=(z.size()-cnt)*pro;
		comp[1][x]%=mod;
		comp[0][x]%=mod;
	}
}
void build(int x)
{
	for (auto i:nei[x])
		build(i);
	if (nei[x].size())
		calc(x);
}
void init(int N, int M,vector<int> P,vector<int> A)
{
	for (int i=1;i<N+M;i++)
	{
		p[i]=P[i];
		nei[P[i]].push_back(i);
	}
	for (int i=0;i<M;i++)
	{
		state[N+i]=A[i];
		comp[A[i]][N+i]=1;
		comp[1-A[i]][N+i]=0;
	}
}
int count_ways(int L, int R)
{
	for (int i=L;i<=R;i++)
	{
		state[i]^=1;
		comp[0][i]^=1;
		comp[1][i]^=1;
	}
	build(0);
	return comp[1][0];
}

Compilation message (stderr)

circuit.cpp: In function 'void calc(int)':
circuit.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (int j=0;j<z.size();j++)
      |                ~^~~~~~~~~

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