oj.uz

Submission #693750

# Submission time Handle Problem Language Result Execution time Memory
693750 2023-02-03T07:48:42 Z Pyqe Digital Circuit (IOI22_circuit) C++17
0 / 100
 12 ms 6540 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);
		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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4944 KB Possible tampering with the output or unexpected termination of the program
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4944 KB Possible tampering with the output or unexpected termination of the program
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4944 KB Possible tampering with the output or unexpected termination of the program
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 6540 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 6540 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4944 KB Possible tampering with the output or unexpected termination of the program
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4944 KB Possible tampering with the output or unexpected termination of the program
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4944 KB Possible tampering with the output or unexpected termination of the program
2 Halted 0 ms 0 KB -