oj.uz

Submission #1077324

# Submission time Handle Problem Language Result Execution time Memory
1077324 2024-08-27T05:20:15 Z Muhammad_Aneeq Digital Circuit (IOI22_circuit) C++17
11 / 100
 3000 ms 11352 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)%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

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.0

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

Subtask #2
7.0 / 7.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 Correct 2 ms 4952 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5164 KB Output is correct
10 Correct 3 ms 5208 KB Output is correct
11 Correct 3 ms 5208 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 8252 KB Output is correct
2 Correct 851 ms 11216 KB Output is correct
3 Correct 808 ms 11352 KB Output is correct
4 Correct 819 ms 11344 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 8252 KB Output is correct
2 Correct 851 ms 11216 KB Output is correct
3 Correct 808 ms 11352 KB Output is correct
4 Correct 819 ms 11344 KB Output is correct
5 Execution timed out 3028 ms 8024 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.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 Correct 2 ms 4952 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5164 KB Output is correct
10 Correct 3 ms 5208 KB Output is correct
11 Correct 3 ms 5208 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct
13 Correct 567 ms 8252 KB Output is correct
14 Correct 851 ms 11216 KB Output is correct
15 Correct 808 ms 11352 KB Output is correct
16 Correct 819 ms 11344 KB Output is correct
17 Execution timed out 3028 ms 8024 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Incorrect 104 ms 5176 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 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Incorrect 104 ms 5176 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -