Submission #1059929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059929		parsadox2	Digital Circuit (IOI22_circuit)	C++17	100 / 100	797 ms	37596 KiB

circuit

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

using namespace std;

const int N = 2e5 + 10 , mod = 1000002022;
int sbt[N] , n , m , zarib[N] , st_tim[N] , fn_tim[N] , tim;
vector <int> p , a , adj[N];

struct SEG1{
	int t[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = m)
	{
		t[node] = 1;
		if(nr - nl == 1)
			return;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);  Build(rc , mid , nr);
	}
	void Add(int val , int l , int r , int node = 1 , int nl = 0 , int nr = m)
	{
		if(r <= nl || nr <= l)
			return;
		if(l <= nl && nr <= r)
		{
			t[node] = 1LL * t[node] * val % mod;
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Add(val , l , r , lc , nl , mid);  Add(val , l , r , rc , mid , nr);
	}
	int Get(int id , int node = 1 , int nl = 0 , int nr = m)
	{
		if(nr - nl == 1)
			return t[node];
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		if(id < mid)
			return 1LL * t[node] * Get(id , lc , nl , mid) % mod;
		else
			return 1LL * t[node] * Get(id , rc , mid , nr) % mod;
	}
} seg1;

struct SEG{
	int sum[2][N << 2];
	int lzy_swp[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = m)
	{
		lzy_swp[node] = 0;
		if(nr - nl == 1)
		{
			sum[0][node] = sum[1][node] = 0;
			sum[a[nl]][node] = seg1.Get(st_tim[nl + n]);
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);  Build(rc , mid , nr);
		sum[0][node] = (sum[0][lc] + sum[0][rc]) % mod;
		sum[1][node] = (sum[1][lc] + sum[1][rc]) % mod;
	}
	void Shift(int node , int lc , int rc)
	{
		if(!lzy_swp[node])
			return;
		lzy_swp[node] = 0;
		swap(sum[0][lc] , sum[1][lc]);
		swap(sum[0][rc] , sum[1][rc]);
		lzy_swp[lc] ^= 1;
		lzy_swp[rc] ^= 1;
	}
	void Update(int l , int r , int node = 1 , int nl = 0 , int nr = m)
	{
		if(r <= nl || nr <= l)
			return;
		if(l <= nl && nr <= r)
		{
			swap(sum[0][node] , sum[1][node]);
			lzy_swp[node] ^= 1;
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Shift(node , lc , rc);
		Update(l , r , lc , nl , mid);
		Update(l , r , rc , mid , nr);
		sum[0][node] = (sum[0][lc] + sum[0][rc]) % mod;
		sum[1][node] = (sum[1][lc] + sum[1][rc]) % mod;
	}
} seg;

void Find_sbt(int v)
{
	sbt[v] = adj[v].size();
	st_tim[v] = tim;
	if(sbt[v] == 0)
	{
		sbt[v] = 1;
		tim++;
		fn_tim[v] = tim;
		return;
	}
	for(auto u : adj[v])
	{
		Find_sbt(u);
		sbt[v] = 1LL * sbt[v] * sbt[u] % mod;
	}
	fn_tim[v] = tim;
}

void Dfs(int v)
{
	if(v >= n)
		return;
	for(int ty = 0 ; ty < 2 ; ty++)
	{
		int prf = 1;
		for(auto u : adj[v])
		{
			seg1.Add(prf , st_tim[u] , fn_tim[u]);
			prf = 1LL * prf * sbt[u] % mod;
		}
		reverse(adj[v].begin() , adj[v].end());
	}
	for(auto u : adj[v])
		Dfs(u);
}

void init(int nn , int mm , vector <int> pp , vector <int> aa)
{
	n = nn;
	m = mm;
	p = pp;
	a = aa;
	for(int i = 1 ; i < n + m ; i++)
		adj[p[i]].push_back(i);
	Find_sbt(0);
	seg1.Build();
	Dfs(0);
	seg.Build();
}

int count_ways(int l , int r)
{
	l -= n;
	r -= n;
	r++;
	seg.Update(l , r);
	return seg.sum[1][1];
}

• 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