oj.uz

Submission #1077561

# Submission time Handle Problem Language Result Execution time Memory
1077561 2024-08-27T08:01:57 Z Faisal_Saqib Digital Circuit (IOI22_circuit) C++17
16 / 100
 3000 ms 16712 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll NP=2e5+100,mod=1000002022;
ll n,m,p[NP],a[NP];
vector<ll> ma[NP];
ll dp[NP][2],lazy[NP],dp1[NP][2],lc[NP],rc[NP];
void compute(int x=0,bool continue_=1)
{
	dp[x][0]=dp[x][1]=0;
	dp1[x][0]=dp1[x][1]=0;
	if(n<=x){
		dp[x][a[x-n]]=1;
		dp1[x][1-a[x-n]]=1;
		return;
	}
	int sz=ma[x].size();
	vector<int> tmp(sz+1);
	// DP 1
	tmp[0]=1;
	for(auto y:ma[x])
	{
		if(continue_)
			compute(y);
		for(int j=sz;j>=0;j--)
		{
			if(j==0)
			{
				tmp[j]=(tmp[j]*dp[y][0])%mod;
			}
			else
			{
				tmp[j]=(tmp[j]*dp[y][0])%mod;
				tmp[j]=(tmp[j] + ((tmp[j-1]*dp[y][1])%mod))%mod;
			}
		}
	}
	int sm=0;
	for(int j=sz;j>=1;j--)
	{
		sm = ( sm + tmp[j] ) % mod;
		dp[x][1] = ( dp[x][1] + sm ) % mod;
	}
	sm=tmp[0];
	for(int j=1;j<=sz;j++)
	{
		dp[x][0] = ( dp[x][0] + sm ) % mod;
		sm = ( sm + tmp[j] ) % mod;
	}
 
 
	// Dp 1
	for(int j=0;j<=sz;j++)tmp[j]=0;
	tmp[0]=1;
	for(auto y:ma[x])
	{
		for(int j=sz;j>=0;j--)
		{
			if(j==0)
			{
				tmp[j]=(tmp[j]*dp1[y][0])%mod;
			}
			else
			{
				tmp[j]=(tmp[j]*dp1[y][0])%mod;
				tmp[j]=(tmp[j] + ((tmp[j-1]*dp1[y][1])%mod))%mod;
			}
		}
	}
	sm=0;
	for(int j=sz;j>=1;j--)
	{
		sm = ( sm + tmp[j] ) % mod;
		dp1[x][1] = ( dp1[x][1] + sm ) % mod;
	}
	sm=tmp[0];
	for(int j=1;j<=sz;j++)
	{
		dp1[x][0] = ( dp1[x][0] + sm ) % mod;
		sm = ( sm + tmp[j] ) % mod;
	}
}
void prepro(int x=0){
	if(n<=x)
	{
		lc[x]=rc[x]=-1;
		return;
	}
	lc[x]=ma[x][0];
	rc[x]=ma[x][1];
	prepro(lc[x]);
	prepro(rc[x]);
}
void push(int v)
{
	if(!lazy[v])return;
	if(lc[v]!=-1)
	{
		lazy[lc[v]]^=lazy[v];
		lazy[rc[v]]^=lazy[v];
	}
	swap(dp[v][0],dp1[v][0]);
	swap(dp[v][1],dp1[v][1]);
	lazy[v]=0;
}
void update(int v,int l,int r,int&ql,int&qr)
{
	push(v);
	if(qr<l or r<ql) // nothing changes here
		return;
	if(ql<=l and r<=qr) // whole subtree to be updated // just swap the values else 
	{
		lazy[v]^=1;
		push(v);
		return;
	}
	int mid=(l+r)/2;
	update(lc[v],l,mid,ql,qr);
	update(rc[v],mid+1,r,ql,qr);
	compute(v,0);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
	n=N,m=M;
	for(ll i=0;i<n+m;i++)
	{
		p[i]=P[i];
		if(p[i]!=-1)ma[p[i]].push_back(i);
	}
	for(ll j=0;j<m;j++)a[j]=A[j];
	prepro();
	compute();
}
 
int count_ways(int L, int R)
{
	L-=n;
	R-=n;
	update(0,0,m-1,L,R);
	push(1);
	return (int)dp[0][1];
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Execution timed out 3092 ms 5088 KB Time limit exceeded
3 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 Correct 2 ms 5208 KB Output is correct
3 Correct 4 ms 5208 KB Output is correct
4 Correct 4 ms 5208 KB Output is correct
5 Correct 4 ms 5208 KB Output is correct
6 Incorrect 3 ms 5208 KB 1st lines differ - on the 1st token, expected: '706880838', found: '295171230'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Execution timed out 3092 ms 5088 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 10704 KB Output is correct
2 Correct 913 ms 16208 KB Output is correct
3 Correct 928 ms 16208 KB Output is correct
4 Correct 961 ms 16208 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 10704 KB Output is correct
2 Correct 913 ms 16208 KB Output is correct
3 Correct 928 ms 16208 KB Output is correct
4 Correct 961 ms 16208 KB Output is correct
5 Correct 889 ms 10960 KB Output is correct
6 Correct 1193 ms 16704 KB Output is correct
7 Correct 1160 ms 16712 KB Output is correct
8 Correct 1099 ms 16208 KB Output is correct
9 Correct 436 ms 5720 KB Output is correct
10 Correct 918 ms 5720 KB Output is correct
11 Correct 919 ms 5804 KB Output is correct
12 Correct 888 ms 5720 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 4 ms 5208 KB Output is correct
4 Correct 4 ms 5208 KB Output is correct
5 Correct 4 ms 5208 KB Output is correct
6 Incorrect 3 ms 5208 KB 1st lines differ - on the 1st token, expected: '706880838', found: '295171230'
7 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 Execution timed out 3092 ms 5088 KB Time limit exceeded
3 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 Execution timed out 3092 ms 5088 KB Time limit exceeded
3 Halted 0 ms 0 KB -