oj.uz

Submission #693751

# Submission time Handle Problem Language Result Execution time Memory
693751 2023-02-03T07:49:11 Z Pyqe Digital Circuit (IOI22_circuit) C++17
18 / 100
 3000 ms 8208 KB 
#include <bits/stdc++.h>
#include "circuit.h"

using namespace std;

const long long dv=1e9+2022;
long long n,m,pr[200069],a[200069],dp[200069],dp2[200069];
vector<long long> al[200069];

void init(int on,int om,vector<int> prr,vector<int> aa)
{
	long long i;
	
	n=on;
	m=om;
	for(i=1;i<=n+m;i++)
	{
		pr[i]=prr[i-1]+1;
	}
	for(i=1;i<=m;i++)
	{
		a[n+i]=aa[i-1];
	}
	for(i=2;i<=n+m;i++)
	{
		al[pr[i]].push_back(i);
	}
}

void dfs(long long x)
{
	if(x<=n)
	{
		long long i,sz=al[x].size(),l;
		vector<long long> mla,mla2;
		
		dp[x]=sz;
		for(i=0;i<sz;i++)
		{
			l=al[x][i];
			dfs(l);
			dp[x]=dp[x]*dp[l]%dv;
		}
		mla.push_back(1);
		for(i=0;i<sz;i++)
		{
			l=al[x][i];
			mla.push_back(mla[i]*dp[l]%dv);
		}
		mla2.push_back(1);
		for(i=sz-1;i>=0;i--)
		{
			l=al[x][i];
			mla2.push_back(mla2[sz-1-i]*dp[l]%dv);
		}
		dp2[x]=0;
		for(i=0;i<sz;i++)
		{
			l=al[x][i];
			dp2[x]=(dp2[x]+dp2[l]*mla[i]%dv*mla2[sz-1-i])%dv;
		}
	}
	else
	{
		dp[x]=1;
		dp2[x]=a[x];
	}
}

int count_ways(int lb,int rb)
{
	long long i;
	
	lb++;
	rb++;
	for(i=lb;i<=rb;i++)
	{
		a[i]^=1;
	}
	dfs(1);
	return dp2[1];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 4 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 4 ms 5072 KB Output is correct
5 Correct 5 ms 5072 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 3 ms 5200 KB Output is correct
11 Correct 6 ms 5200 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 4 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 5000 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct
13 Correct 5 ms 5072 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5072 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 6 ms 5200 KB Output is correct
20 Correct 4 ms 5072 KB Output is correct
21 Correct 3 ms 5072 KB Output is correct
22 Correct 4 ms 5072 KB Output is correct
23 Correct 4 ms 5072 KB Output is correct
24 Correct 4 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 4 ms 5072 KB Output is correct
27 Correct 4 ms 5072 KB Output is correct
28 Correct 4 ms 5072 KB Output is correct
29 Correct 3 ms 5072 KB Output is correct
30 Correct 3 ms 5072 KB Output is correct
31 Correct 3 ms 5200 KB Output is correct
32 Correct 5 ms 5072 KB Output is correct
33 Correct 3 ms 5072 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 3 ms 5080 KB Output is correct
36 Correct 4 ms 5200 KB Output is correct
37 Correct 6 ms 5328 KB Output is correct
38 Correct 4 ms 5328 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct
40 Correct 3 ms 5072 KB Output is correct
41 Correct 3 ms 5072 KB Output is correct
42 Correct 3 ms 5072 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 8208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 8208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 4 ms 5072 KB Output is correct
5 Correct 5 ms 5072 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 3 ms 5200 KB Output is correct
11 Correct 6 ms 5200 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct
13 Execution timed out 3039 ms 8208 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 4 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 5000 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct
13 Correct 5 ms 5072 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5072 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 6 ms 5200 KB Output is correct
20 Correct 4 ms 5072 KB Output is correct
21 Correct 3 ms 5072 KB Output is correct
22 Correct 4 ms 5072 KB Output is correct
23 Correct 4 ms 5072 KB Output is correct
24 Correct 4 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 4 ms 5072 KB Output is correct
27 Correct 4 ms 5072 KB Output is correct
28 Correct 4 ms 5072 KB Output is correct
29 Correct 3 ms 5072 KB Output is correct
30 Correct 3 ms 5072 KB Output is correct
31 Correct 3 ms 5200 KB Output is correct
32 Correct 5 ms 5072 KB Output is correct
33 Correct 3 ms 5072 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 3 ms 5080 KB Output is correct
36 Correct 4 ms 5200 KB Output is correct
37 Correct 6 ms 5328 KB Output is correct
38 Correct 4 ms 5328 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct
40 Correct 3 ms 5072 KB Output is correct
41 Correct 3 ms 5072 KB Output is correct
42 Correct 3 ms 5072 KB Output is correct
43 Execution timed out 3053 ms 5340 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 4 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 5000 KB Output is correct
12 Correct 4 ms 5072 KB Output is correct
13 Correct 5 ms 5072 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5072 KB Output is correct
16 Correct 4 ms 5072 KB Output is correct
17 Correct 3 ms 5072 KB Output is correct
18 Correct 3 ms 5200 KB Output is correct
19 Correct 6 ms 5200 KB Output is correct
20 Correct 4 ms 5072 KB Output is correct
21 Correct 3 ms 5072 KB Output is correct
22 Correct 4 ms 5072 KB Output is correct
23 Correct 4 ms 5072 KB Output is correct
24 Correct 4 ms 5072 KB Output is correct
25 Correct 4 ms 5072 KB Output is correct
26 Correct 4 ms 5072 KB Output is correct
27 Correct 4 ms 5072 KB Output is correct
28 Correct 4 ms 5072 KB Output is correct
29 Correct 3 ms 5072 KB Output is correct
30 Correct 3 ms 5072 KB Output is correct
31 Correct 3 ms 5200 KB Output is correct
32 Correct 5 ms 5072 KB Output is correct
33 Correct 3 ms 5072 KB Output is correct
34 Correct 3 ms 5072 KB Output is correct
35 Correct 3 ms 5080 KB Output is correct
36 Correct 4 ms 5200 KB Output is correct
37 Correct 6 ms 5328 KB Output is correct
38 Correct 4 ms 5328 KB Output is correct
39 Correct 3 ms 5072 KB Output is correct
40 Correct 3 ms 5072 KB Output is correct
41 Correct 3 ms 5072 KB Output is correct
42 Correct 3 ms 5072 KB Output is correct
43 Execution timed out 3039 ms 8208 KB Time limit exceeded
44 Halted 0 ms 0 KB -