Submission #1235750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235750		MuhammadSaram	디지털 회로 (IOI22_circuit)	C++20	0 / 100	8 ms	5904 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 2e5  + 1;
const ll mod = 1e9 + 2022;

int n, m, par[M];
vector<int> nei[M],p;
ll dp[M][2];

void calc(int u)
{
	int x=nei[u][0], y=nei[u][1];
	dp[u][1]=0;
	for (int i=0;i<=1;i++)
		for (int j=0;j<=1;j++)
			dp[u][1]+=(i+j)*dp[x][i]*dp[y][j];
	dp[u][1]%=mod;
	dp[u][0]=2*(dp[x][0]+dp[x][1])*(dp[x][0]+dp[x][1])-dp[u][1];
	dp[u][0]%=mod;
}

void dfs(int u)
{
	if (nei[u].empty()) return;
	for (int i:nei[u])
		par[i]=u,dfs(i);
	calc(u);
}

void init(int n1, int m1, vector<int> P, vector<int> a)
{
	n=n1, m=m1;
	for (int i=1;i<n+m;i++)
		nei[p[i]].push_back(i);
	for (int i=0;i<m;i++)
		dp[i+n][0]=!a[i], dp[i+n][1]=a[i];
	dfs(0);
}

int count_ways(int l, int r)
{
	swap(dp[l+n][0],dp[l+n][1]);
	while (l)
		calc(par[l]),l=par[l];
}

Compilation message (stderr)

circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:50:1: warning: no return statement in function returning non-void [-Wreturn-type]
   50 | }
      | ^

• 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