Submission #1030900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030900		0npata	Digital Circuit (IOI22_circuit)	C++17	100 / 100	774 ms	34260 KiB

circuit

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

using namespace std;

#define vec vector
#define int long long
#define arr array

const int MX = 200'005;

vec<int32_t> a;
vec<int> tree[MX];
int tot[MX];
int n, m;
const int MXM = 100'005;
const int MOD = 1'000'002'022;
int contr[MXM];

struct SegLazy {
	bool flip = false;

	SegLazy merge(SegLazy other) {
		return {flip ^ other.flip};
	}
};

struct SegNode {
	arr<int, 2> sums = {0, 0};

	SegNode merge(SegNode other) {
		return {{sums[0]+other.sums[0], sums[1]+other.sums[1]}};
	}

	SegNode upd(SegLazy lazy) {
		if(lazy.flip) {
			return {{sums[1], sums[0]}};
		}
		else {
			return {{sums[0], sums[1]}};
		}
	}
};


struct SegTree {
	int n;
	vec<SegNode> data;
	vec<SegLazy> lazy;

	SegTree(int in) {
		n = 1;
		while(n < in) n *= 2;
		data = vec<SegNode>(n*2);
		lazy = vec<SegLazy>(n*2);
	}

	void pull(int i) {
		data[i] = data[i*2].merge(data[i*2+1]);
	}

	void set(int i, SegNode val) {
		i += n;
		data[i] = val;
		while(i > 1) {
			i /= 2;
			pull(i);
		}
	}

	void push(int i) {
		data[i] = data[i].upd(lazy[i]);
		if(i*2 >= n*2) {
			lazy[i] = {};
			return;
		}
		lazy[i*2] = lazy[i*2].merge(lazy[i]);
		lazy[i*2+1] = lazy[i*2+1].merge(lazy[i]);
		lazy[i] = {};
	}


	void upd(int l, int r, SegLazy val) {
		_upd(l, r, 1, 0, n, val);
	}

	void _upd(int l, int r, int ti, int tl, int tr, SegLazy val) {
		//cerr << tl << ' ' << tr << '\n';
		push(ti);
		if(l >= tr || r <= tl) return;
		if(l <= tl && r >= tr) {
			lazy[ti] = val;
			push(ti);
			return;
		}

		int tm = (tl+tr)/2;
		_upd(l, r, ti*2, tl, tm, val);
		_upd(l, r, ti*2+1, tm, tr, val);
		pull(ti);
	}
};

SegTree st(0);

void dfs1(int u) {
	if(u >= n) {
		tot[u] = 1;
		return;
	}
	tot[u] = tree[u].size();
	for(int v : tree[u]) {
		dfs1(v);
		tot[u] *= tot[v];
		tot[u] %= MOD;
	}
}

void dfs2(int u, int top) {
	if(u >= n) {
		contr[u-n] = top;
		return;
	}
	vec<int> pref_mul(tree[u].size()+1);
	vec<int> suf_mul(tree[u].size()+1);

	pref_mul[0] = 1;
	suf_mul[0] =1;

	for(int i = 0; i<tree[u].size(); i++) {
		pref_mul[i+1] = pref_mul[i]*tot[tree[u][i]];
		pref_mul[i+1] %= MOD;
		suf_mul[i+1] = suf_mul[i]*tot[tree[u][tree[u].size()-i-1]];
		suf_mul[i+1] %= MOD;
	}

	for(int i = 0; i<tree[u].size(); i++) {
		dfs2(tree[u][i], (((top*pref_mul[i])%MOD)*suf_mul[tree[u].size()-i-1]) % MOD);
	}
}


void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
	n = N;
	m = M;
	a = A;

	for(int i = 1; i<N+M; i++) {
		tree[P[i]].push_back(i);
	}

	dfs1(0);
	dfs2(0, 1);

	st = SegTree(m);
	for(int i = 0; i<m; i++) {
		//cerr << contr[i] << ' ';
		SegNode node = {{0, contr[i]}};
		st.set(i, node);
		st.upd(i, i+1, {A[i]});
	}
	//cerr << '\n';
	//cerr << st.data[1].sums[0] << '\n';
}

int32_t count_ways(int32_t L, int32_t R) {
	//cerr << "QUERY: " << L << ' ' << R << '\n';
	st.upd(L-n, R+1-n, {true});
	return st.data[1].sums[0] % MOD;
}

Compilation message (stderr)

circuit.cpp: In member function 'SegLazy SegLazy::merge(SegLazy)':
circuit.cpp:24:16: warning: narrowing conversion of '(((int)((SegLazy*)this)->SegLazy::flip) ^ ((int)other.SegLazy::flip))' from 'int' to 'bool' [-Wnarrowing]
   24 |   return {flip ^ other.flip};
      |           ~~~~~^~~~~~~~~~~~
circuit.cpp: In function 'void dfs2(long long int, long long int)':
circuit.cpp:130:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |  for(int i = 0; i<tree[u].size(); i++) {
      |                 ~^~~~~~~~~~~~~~~
circuit.cpp:137:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |  for(int i = 0; i<tree[u].size(); i++) {
      |                 ~^~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int32_t, int32_t, std::vector<int>, std::vector<int>)':
circuit.cpp:160:24: warning: narrowing conversion of 'A.std::vector<int>::operator[](((std::vector<int>::size_type)i))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'bool' [-Wnarrowing]
  160 |   st.upd(i, i+1, {A[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