Submission #774367

#	Time	Username	Problem	Language	Result	Execution time	Memory
774367		GusterGoose27	Digital Circuit (IOI22_circuit)	C++17	100 / 100	970 ms	25344 KiB

circuit

#include "circuit.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1000002022;
const int MAXN = 2e5;

bool init_active[MAXN];
int weight[MAXN];
vector<int> edges[MAXN];
int n, m;
int cur_mult;

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	int active;
	int tot;
	bool lz;
	stree(int lv, int rv) {
		lz = 0;
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid);
			r = new stree(mid+1, rp);
			reupd();
		}
		else {
			tot = weight[lp];
			if (init_active[lp]) active = weight[lp];
			else active = 0;
		}
	}
	void reupd() {
		active = (l->active+r->active)%MOD;
		tot = (l->tot+r->tot)%MOD;
	}
	void setlz(bool nlz) {
		if (!nlz) return;
		lz ^= 1;
		active = (MOD+tot-active)%MOD;
	}
	void prop() {
		if (l) {
			l->setlz(lz);
			r->setlz(lz);
		}
		lz = 0;
	}
	void rev(int lv, int rv) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			setlz(1);
			return;
		}
		prop();
		l->rev(lv, rv);
		r->rev(lv, rv);
		reupd();
	}
};

void dfs(int cur, bool rev) {
	if (cur >= n-m) {
		// cout << cur_mult << "\n";
		weight[cur-n+m] = ((ll)weight[cur-n+m]*cur_mult)%MOD;
		return;
	}
	if (!rev) {
		for (int i = 0; i < edges[cur].size(); i++) {
			int nxt = edges[cur][i];
			dfs(nxt, rev);
		}
	}
	else {
		for (int i = edges[cur].size()-1; i >= 0; i--) {
			int nxt = edges[cur][i];
			dfs(nxt, rev);
		}
	}
	cur_mult = ((ll)cur_mult*edges[cur].size())%MOD;
	// cout << cur_mult << "\n";
}

stree *tree;

void init(int N, int M, vector<int> par, vector<int> act) {
	n = N+M;
	m = M;
	for (int i = 1; i < n; i++) {
		edges[par[i]].push_back(i);
	}
	for (int i = 0; i < m; i++) {
		init_active[i] = act[i];
		weight[i] = 1;
	}
	cur_mult = 1;
	dfs(0, 0);
	cur_mult = 1;
	dfs(0, 1);
	// for (int i = 0; i < m; i++) cout << weight[i] << ' ';
	// cout << "\n";
	tree = new stree(0, m-1);
}

int count_ways(int l, int r) {
	tree->rev(l-n+m, r-n+m);
	return tree->active;
}

Compilation message (stderr)

circuit.cpp: In function 'void dfs(int, bool)':
circuit.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (int i = 0; i < edges[cur].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