Submission #637192

#	Time	Username	Problem	Language	Result	Execution time	Memory
637192		blue	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1154 ms	46092 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])));
	}
}

struct segtree
{
	int l;
	int r;
	ll v[2];

	int lp = 0; //1 -> flip 0 and 1

	segtree* left = NULL;
	segtree* right = NULL;

	segtree()
	{
		;
	}

	segtree(int L, int R)
	{
		l = L;
		r = R;
		if(l == r)
		{
			if(A[l])
			{
				v[0] = coeff[l];
				v[1] = 0;
			}
			else
			{
				v[0] = 0;
				v[1] = coeff[l];
			}
		}
		else
		{
			int m = (l+r)/2;
			left = new segtree(l, m);
			right = new segtree(m+1, r);

			v[0] = ad(left->v[0], right->v[0]);
			v[1] = ad(left->v[1], right->v[1]);
		}	
	}

	void flip(int L, int R)
	{
		if(R < l || r < L) return;
		else if(L <= l && r <= R)
		{
			lp = !lp;
			swap(v[0], v[1]);
		}
		else
		{
			left->flip(L, R);
			right->flip(L, R);

			v[0 ^ lp] = ad(left->v[0], right->v[0]);
			v[1 ^ lp] = ad(left->v[1], right->v[1]);
		}
	}
};

segtree S;

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);

	S = segtree(N, N+M-1);
}

int count_ways(int L, int R)
{
	S.flip(L, R);
	return S.v[0];
}

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