Submission #1077324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077324		Muhammad_Aneeq	Digital Circuit (IOI22_circuit)	C++17	11 / 100	3028 ms	11352 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)%mod;
		comp[0][x]+=((z.size()-cnt)*pro)%mod;
		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 up(int x)
{
	if (nei[x].size())
		calc(x);
	if (x!=0)
		up(p[x]);
}
void init(int N, int M,vector<int> P,vector<int> A)
{
	p[0]=-1;
	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;
	}
	build(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;
	}
	if (L==R)
		up(L);
	else
		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: 4 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11