Submission #1191805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191805		catch_me_if_you_can	Digital Circuit (IOI22_circuit)	C++20	100 / 100	392 ms	33820 KiB

circuit

#include<bits/stdc++.h>
#include "circuit.h"
using namespace std;
#define fint signed
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back


const int MX = 2e5+5;
const int mod = 1e9+2022;

int NS, MS;

struct segment_tree
{
	vector<int> tree; vector<int> sum; vector<bool> lazy;
	void build(const vector<fint> &val, const vector<fint> &st, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l == r)
		{
			sum[id] = val[m];
			tree[id] = (st[m] ? val[m] : 0ll);
			return;
		}
		build(val, st, 2*id, l, m);
		build(val, st, 2*id+1, m+1, r);
		tree[id] = (tree[2*id]+tree[2*id+1])%mod;
		sum[id] = (sum[2*id]+sum[2*id+1])%mod;
		return;
	}
	void push(int id)
	{
		if(!lazy[id])
			return;
		lazy[2*id] = lazy[2*id]^1;
		lazy[2*id+1] = lazy[2*id+1]^1;
		tree[2*id] = (sum[2*id]-tree[2*id]+mod)%mod;
		tree[2*id+1] = (sum[2*id+1]-tree[2*id+1]+mod)%mod;
		lazy[id] = 0;
		return;
	}
	void init(const vector<fint> &val, const vector<fint> &st, int n)
	{
		tree.resize(4*n+5);
		sum.resize(4*n+5);
		lazy.assign(4*n+5, false);
		build(val, st, 1, 0, n-1);
		return;
	}
	void upd(int ql, int qr, int id, int l, int r)
	{
		//cout << "Called " << endl;
		if(qr < l || r < ql)
			return;
		if((ql <= l) && (r <= qr))
		{
			tree[id] = (sum[id]-tree[id]+mod)%mod;
			lazy[id] = lazy[id]^1;
			return;
		}
		push(id);
		int m = (l+r)/2;
		upd(ql, qr, 2*id, l, m);
		upd(ql, qr, 2*id+1, m+1, r);
		tree[id] = (tree[2*id]+tree[2*id+1])%mod;
		return;
	}
	int Q()
	{
		return tree[1];
	}
};

segment_tree work;

int oth[MX];
int prod[MX];

vector<fint> val;
vector<int> adj[MX];

void dfs(int u)
{
	prod[u] = max(1ll, (int)adj[u].size());
	vector<int> w;
	for(int v: adj[u])
	{
		dfs(v);
		w.pb(prod[v]);
		prod[u]*=prod[v]; prod[u]%=mod;
	}
	//cout << "Running u = " << u << endl;
	int n = w.size();
	if(w.empty())
		return;
	int pref[n];
	int suff[n];
	pref[0] = w[0];
	for(int i = 1; i < n; i++)
		pref[i] = (pref[i-1]*w[i])%mod;
	suff[n-1] = w[n-1];
	for(int i = n-2; i >= 0; i--)
		suff[i] = (suff[i+1]*w[i])%mod;
	int cnt = 0;
	for(int v: adj[u])
	{
		oth[v] = 1;
		if(cnt > 0)
			oth[v]*=pref[cnt-1];
		if(cnt < (n-1))
			oth[v]*=suff[cnt+1];
		oth[v]%=mod;
		cnt++;
	}
	return;
}

void dfs2(int u, int VL = 1)
{
	if(u >= NS)
	{
		//cout << "Called u = " << u << " and VL = " << VL << endl;
		val[u-NS] = VL;
	}
	for(int v: adj[u])
	{
		int VL_p = (VL*oth[v])%mod;
		dfs2(v, VL_p);
	}
	return;
}

void init(fint n, fint m, vector<fint> p, vector<fint> a)
{
	NS = n;
	MS = m;
	for(int i = 0; i < n+m; i++)
		adj[i].clear();
	for(int i = 1; i < n+m; i++)
		adj[p[i]].pb(i);
	val.resize(m);
	dfs(0); dfs2(0);
	/*cout << "r - ";
	for(int i = n; i < n+m; i++)
		cout << val[i-n] << " ";
	cout << "\n";*/
	//cout << "Hey " << endl;
	work.init(val, a, m);
	return;
}

fint count_ways(fint L, fint R)
{
	int l = L-NS;
	int r = R-NS;
	work.upd(l, r, 1, 0, MS-1);
	return (fint)work.Q();
}

• 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