Submission #831032

#	Time	Username	Problem	Language	Result	Execution time	Memory
831032		caganyanmaz	Digital Circuit (IOI22_circuit)	C++17	100 / 100	978 ms	37688 KiB

circuit

#include <bits/stdc++.h>
#define mp(x...) array<int, 2>({x})
#define pb push_back
using namespace std;
#include "circuit.h"

constexpr static int MXN = 2e5;
constexpr static int MOD = 1000002022;
constexpr static int MXST = MXN<<2;
int mul() { return 1; }
template<typename... V>
int mul(int64_t a, V... v) { return (a* mul(v...)) % MOD; }
int add() { return 0; }
template<typename... V>
int add(int a, V... v) { return (a+add(v...)) % MOD; }


//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

int n, m;
vector<int> p;
vector<int> a;


vector<int> g[MXN];
int factor[MXN];
int pcount[MXN];
void calculate(int i);
static inline int mul(int64_t a, int64_t b) { return (a*b) % MOD; }
static inline int add(int a, int b) { return (a+b) % MOD; }

struct SegTree
{
	int n;
	array<int, 2> data[MXST];
	bitset<MXST> lazy;
	array<int, 2> merge(array<int, 2> a, array<int, 2> b)
	{
		return mp(add(a[0], b[0]), add(a[1], b[1]));
	}
	void push(int l, int r, int index)
	{
		if (lazy[index] == 1)
			swap(data[index][0], data[index][1]);
		if (r - l > 1)
		{
			lazy[index<<1] = lazy[index<<1] ^  lazy[index];
			lazy[(index<<1)|1] = lazy[(index<<1)|1] ^ lazy[index];
		}
		lazy[index] = 0;
	}
	void build(int l, int r, int index, vector<int>& a, vector<int>& f)
	{
		if (r - l == 1)
		{
			data[index][0] = mul((a[l]^1), f[l]);
			data[index][1] = mul(a[l], f[l]);
			debug(l, data[index]);
			return;
		}
		int m = l+r>>1;
		build(l, m, index<<1, a, f);
		build(m, r, (index<<1)|1, a, f);
		data[index] = merge(data[index<<1], data[(index<<1)|1]);
		debug(l, r, data[index]);
	}
	void toggle(int l, int r, int index, int ss, int ee)
	{
		push(l, r, index);
		if (ss >= r || l >= ee)
			return;
		if (ee >= r && l >= ss)
		{
			lazy[index] = lazy[index] ^ 1;
			push(l, r, index);
			debug(l, r, data[index]);
			return;
		}
		int m = l+r>>1;
		toggle(l, m, index<<1, ss, ee);
		toggle(m, r, (index<<1)|1, ss, ee);
		data[index] = merge(data[index<<1], data[(index<<1)|1]);
		debug(l, r, data[index]);
	}
	int query(int l, int r, int index, int ss, int ee)
	{
		push(l, r, index);
		if (ss >= r || l >= ee)
			return 0;
		if (ee >= r && l >= ss)
			return data[index][1];
		int m = l+r>>1;
		int lres = query(l, m, index<<1, ss, ee);
		int rres = query(m, r, (index<<1)|1, ss, ee);
		return add(lres, rres);
	}
};
SegTree st;

void dfs1(int node)
{
	if (node >= n)
		pcount[node] = 1;
	else
		pcount[node] = g[node].size();
	for (int c : g[node])
	{
		dfs1(c);
		pcount[node] = mul(pcount[node], pcount[c]);
	}
}

void dfs2(int node)
{
	vector<int> pf(g[node].size()+1), sf(g[node].size()+1);
	pf[0] = 1, sf[g[node].size()] = 1;
	for (int i = 1; i <= g[node].size(); i++)
		pf[i] = mul(pf[i-1], pcount[g[node][i-1]]);
	for (int i = g[node].size()-1; i >= 0; i--)
		sf[i] = mul(sf[i+1], pcount[g[node][i]]);
	for (int i = 0; i < g[node].size(); i++)
	{
		int c = g[node][i];
		factor[c] = mul(factor[node],pf[i], sf[i+1]);
		dfs2(c);
	}
}

void init(int N, int M, vector<int> P, vector<int> A) 
{
	n = N;
	m = M;
	p = P;
	a = A;
	for (int i = 1; i < n+m; i++)
		g[p[i]].pb(i);
	dfs1(0);
	factor[0] = 1;
	dfs2(0);
	vector<int> as;
	for (int i = n; i < n+m; i++)
		as.pb(factor[i]);
	st.build(0, m, 1, a, as);
}

int count_ways(int l, int r) 
{
	debug(l-n, r-n+1);
	st.toggle(0, m, 1, l-n, r-n+1);
	return st.query(0, m, 1, 0, m);
}

Compilation message (stderr)

circuit.cpp: In member function 'void SegTree::build(int, int, int, std::vector<int>&, std::vector<int>&)':
circuit.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |   int m = l+r>>1;
      |           ~^~
circuit.cpp: In member function 'void SegTree::toggle(int, int, int, int, int)':
circuit.cpp:84:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |   int m = l+r>>1;
      |           ~^~
circuit.cpp: In member function 'int SegTree::query(int, int, int, int, int)':
circuit.cpp:97:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |   int m = l+r>>1;
      |           ~^~
circuit.cpp: In function 'void dfs2(int)':
circuit.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |  for (int i = 1; i <= g[node].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
circuit.cpp:126:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |  for (int i = 0; i < g[node].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~

• 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