Submission #637191

#	Time	Username	Problem	Language	Result	Execution time	Memory
637191		blue	Digital Circuit (IOI22_circuit)	C++17	50 / 100	3037 ms	14420 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define sz(x) int(x.size())

const ll mod = 1'000'002'022;

ll ad(ll a, ll b)
{
	return (a+b)%mod;
}

ll mul(ll a, ll b)
{
	return (a*b)%mod;
}

const int mx = 200'000;

vll Z(1 + mx, 0);
vll Zprod(1 + mx, 1);

vll coeff(1 + mx, 0);


vi children[1 + mx];
int N, M;

vi A;

ll res = 0;

void dfs(int u)
{
	for(int v : children[u])
	{
		Z[u]++;
		dfs(v);

		if(Z[v] != 0)
			Zprod[u] = mul(Zprod[u], Zprod[v]);
	}

	if(Z[u] != 0)
		Zprod[u] = mul(Zprod[u], Z[u]);

	// cerr << u << " : " << Z[u] << " | " << Zprod[u] << '\n';
}

void dfs2(int u, ll curr)
{
	coeff[u] = curr;
	// cerr << u << " -> " << curr << '\n';

	ll fwd[1 + sz(children[u]) + 1];
	ll bwd[1 + sz(children[u]) + 1];

	fwd[0] = 1;
	for(int e = 1; e <= sz(children[u]); e++)
		fwd[e] = mul(fwd[e-1], Zprod[ children[u][e - 1] ]);

	bwd[sz(children[u]) + 1] = 1;
	for(int e = sz(children[u]); e >= 1; e--)
		bwd[e] = mul(bwd[e+1], Zprod[ children[u][e - 1] ]);

	for(int e = 1; e <= sz(children[u]); e++)
	{
		// cerr << e << " : " << curr << ' ' << fwd[e-1] << ' ' << bwd[e+1] << '\n';
		dfs2(children[u][e - 1], mul(curr, mul(fwd[e-1], bwd[e+1])));
	}
}

void init(int N_, int M_, vi P_, vi A_)
{
	N = N_;
	M = M_;

	for(int i = 1; i < N+M; i++)
		children[P_[i]].push_back(i);

	dfs(0);
	dfs2(0, 1);

	A = vi(N, -1);
	for(int a : A_)
		A.push_back(a);

	// cerr << depth[1] << ' ' << depth[2] << '\n';

	for(int i = N; i < N+M; i++)
		res = ad(res, mul(A[i], coeff[i]));

	// cerr << "res = " << res << '\n';

	// for(int f : A)
	// 	cerr << f << '\n';
}

int count_ways(int L, int R)
{
	for(int i = L; i <= R; i++)
	{
		// res = ad(res, mul((!A[i]) - A[i], coeff[i]));
		if(A[i] == 0)
			res = ad(res, coeff[i]);
		else
			res = ad(res, mod - coeff[i]);
		A[i] = !A[i];
	}

	return res;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 28 / 28
• Subtask 8: 0 / 11