Submission #681577

#	Time	Username	Problem	Language	Result	Execution time	Memory
681577		Justin1	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1062 ms	36608 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int mod = 1e9 + 2022;
int n, m, k, x, y, z;
int val[200005], cont[200005], cur[200005];
int seg[1'000'005], lzy[1'000'005], ps[200005];
vector<signed> par, gph[200005];

void dfs(int id) {
	val[id] = id >= n ? 1 : gph[id].size();
	for (auto i : gph[id]) dfs(i), val[id] = val[id] * val[i] % mod;
}

void dfs2(int id, int cur) {
	if (id >= n) cont[id - n + 1] = cur;
	int post[gph[id].size()+2], pre = 1;
	post[gph[id].size()+1] = 1;
	for (int i = gph[id].size(); i >= 1; i--) post[i] = post[i+1] * val[gph[id][i-1]] % mod;
	for (int i = 1; i <= gph[id].size(); i++) {
		dfs2(gph[id][i-1], cur * pre % mod * post[i+1] % mod);
		pre = pre * val[gph[id][i-1]] % mod;
	}
}

void push(int id, int l, int r) {
	if (!lzy[id]) return;
	lzy[id] = 0;
	int mid = (l + r) / 2;
	seg[id * 2] = ps[mid] - ps[l-1] - seg[id * 2];
	seg[id * 2 + 1] = ps[r] - ps[mid] - seg[id * 2 + 1];
	lzy[2 * id] ^= 1;
	lzy[2 * id + 1] ^= 1;
}

void upd(int t1, int t2, int id = 1, int l = 1, int r = 100000) {
	push(id, l, r);
	if (r < t1 || t2 < l) return;
	if (t1 <= l && r <= t2) {
		seg[id] = ps[r] - ps[l-1] - seg[id];
		lzy[id] ^= 1;
		return;
	}
	int mid = (l + r) / 2;
	upd(t1, t2, id * 2, l, mid), upd(t1, t2, id * 2 + 1, mid + 1, r);
	seg[id] = (seg[id * 2] + seg[id * 2 + 1]) % mod;
}

void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
	n = N, m = M, par = P;
	for (int i = 1; i < n + m; i++) gph[P[i]].push_back(i);
	for (int i = n; i < n + m; i++) cur[i] = A[i-n];
	dfs(0);
	dfs2(0, 1);
	for (int i = 1; i <= m; i++) ps[i] = (ps[i-1] + cont[i]) % mod;
	for (int i = 1; i <= m; i++) if (A[i-1]) upd(i, i);
}
 
signed count_ways(signed L, signed R) {
	upd(L - n + 1, R - n + 1);
	return (seg[1] % mod + mod) % mod;
}

Compilation message (stderr)

circuit.cpp: In function 'void dfs2(long long int, long long int)':
circuit.cpp:22:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 1; i <= gph[id].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