Submission #693750

#	Time	Username	Problem	Language	Result	Execution time	Memory
693750		Pyqe	Digital Circuit (IOI22_circuit)	C++17	0 / 100	12 ms	6540 KiB

circuit

#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);
		cout<<"ed "<<pr[i]<<" "<<i<<endl;
	}
}

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: 0 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11