oj.uz

Submission #1077301

# Submission time Handle Problem Language Result Execution time Memory
1077301 2024-08-27T05:03:02 Z Muhammad_Aneeq Digital Circuit (IOI22_circuit) C++17
0 / 100
 552 ms 7888 KB 
#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;
		if (cnt<z.size()/2)
			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 up(int x)
{
	if (x==-1)
		return;
	calc(x);
	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;
	}
}
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(p[L]);
	else
		build(0);
	return comp[1][0];
}

Compilation message

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++)
      |                ~^~~~~~~~~
circuit.cpp:27:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   if (cnt<z.size()/2)
      |       ~~~^~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Incorrect 86 ms 5180 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '52130940', found: '257116406'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Incorrect 86 ms 5180 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 552 ms 7888 KB 1st lines differ - on the 1st token, expected: '431985922', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 552 ms 7888 KB 1st lines differ - on the 1st token, expected: '431985922', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '52130940', found: '257116406'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Incorrect 86 ms 5180 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Incorrect 86 ms 5180 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -