Submission #736638

#	Time	Username	Problem	Language	Result	Execution time	Memory
736638		jk410	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1311 ms	35912 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000002022;
struct node {
	ll sum, sum2;
};
node operator+(const node& a, const node& b) {
	node ret;
	ret.sum = (a.sum + b.sum) % MOD;
	ret.sum2 = (a.sum2 + b.sum2) % MOD;
	return ret;
}
struct segmentTree {
	vector<node> tree;
	vector<int> lazy;
	void init(int n) {
		int sz = (1 << (int)ceil(log2(n)) + 1);
		tree.resize(sz);
		lazy.resize(sz);
	}
	node updateVal(int x, node v, int l, int r, int n) {
		if (r < x || x < l)
			return tree[n];
		if (l == r)
			return tree[n] = v;
		int m = (l + r) >> 1;
		return tree[n] = updateVal(x, v, l, m, n << 1) + updateVal(x, v, m + 1, r, n << 1 | 1);
	}
	void propagate(int l, int r, int n) {
		if (!lazy[n])
			return;
		swap(tree[n].sum, tree[n].sum2);
		if (l != r) {
			lazy[n << 1] = !lazy[n << 1];
			lazy[n << 1 | 1] = !lazy[n << 1 | 1];
		}
		lazy[n] = 0;
	}
	node update(int lx, int rx, int l, int r, int n) {
		propagate(l, r, n);
		if (r < lx || rx < l)
			return tree[n];
		if (lx <= l && r <= rx) {
			lazy[n] = !lazy[n];
			propagate(l, r, n);
			return tree[n];
		}
		int m = (l + r) >> 1;
		return tree[n] = update(lx, rx, l, m, n << 1) + update(lx, rx, m + 1, r, n << 1 | 1);
	}
};

int n, m;
vector<int> child[200000];
ll degs[200000];
ll dp[200000];
segmentTree st;

ll dfs(int v) {
	int sz = (int)child[v].size();
	ll& ret = degs[v] = max(sz, 1);
	for (int i : child[v])
		ret = ret * dfs(i) % MOD;
	return ret;
}

void dfs2(int v, ll tmp) {
	dp[v] = tmp;
	int sz = (int)child[v].size();
	vector<ll> pre(sz + 1), suf(sz + 1);
	pre[0] = 1;
	for (int i = 1; i <= sz; i++)
		pre[i] = pre[i - 1] * degs[child[v][i - 1]] % MOD;
	suf[sz] = 1;
	for (int i = sz - 1; i >= 0; i--)
		suf[i] = suf[i + 1] * degs[child[v][i]] % MOD;
	for (int i = 0; i < sz; i++)
		dfs2(child[v][i], tmp * pre[i] % MOD * suf[i + 1] % MOD);
}

void init(int _n, int _m, vector<int> p, vector<int> a) {
	n = _n;
	m = _m;
	for (int i = 0; i < n + m; i++)
		child[p[i]].push_back(i);
	dfs(0);
	dfs2(0, 1);
	st.init(m);
	for (int i = 0; i < m; i++) {
		node cur = { dp[i + n],0 };
		if (!a[i])
			swap(cur.sum, cur.sum2);
		st.updateVal(i, cur, 0, m - 1, 1);
	}
}

int count_ways(int l, int r) {
	st.update(l - n, r - n, 0, m - 1, 1);
	st.propagate(0, m - 1, 1);
	return st.tree[1].sum;
}

Compilation message (stderr)

circuit.cpp: In member function 'void segmentTree::init(int)':
circuit.cpp:19:37: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   19 |   int sz = (1 << (int)ceil(log2(n)) + 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