Submission #925520

#	Time	Username	Problem	Language	Result	Execution time	Memory
925520		beaboss	Digital Circuit (IOI22_circuit)	C++17	100 / 100	749 ms	47196 KiB

circuit

// Source: https://oj.uz/problem/view/IOI22_circuit
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }

#define lc (i << 1)
#define rc (i << 1) + 1

const ll N = 2e5 + 10;

const ll MOD = 1e9 + 2022;

ll n, m;
ll p[N], contrib[N], sub[N];
vi adj[N];

void calc_sub(ll cur) {
	sub[cur] = 1;
	for (auto val: adj[cur]) {
		calc_sub(val);
		sub[cur] = sub[cur] * sub[val] % MOD;
	}
	if (adj[cur].size()) sub[cur] = sub[cur] * adj[cur].size() % MOD;
	// cout <<  ' ' << cur << sub[cur] << adj[cur].size() << endl;
}

void dfs(ll cur, ll prod = 1) {
	// cout << cur << prod << endl;
	contrib[cur]=prod;

	vi pref(adj[cur].size()), suff(adj[cur].size());

	FOR(i, 0, adj[cur].size()) {
		if (i) pref[i] = pref[i-1];
		else pref[i]=1;
		pref[i] = pref[i] * sub[adj[cur][i]] % MOD;
	}

	for (ll i = adj[cur].size() - 1; i >= 0; i--) {
		if (i != adj[cur].size() - 1) suff[i] = suff[i + 1];
		else suff[i]=1;
		suff[i] = suff[i] * sub[adj[cur][i]] % MOD;
	}

	FOR(i, 0, adj[cur].size()) {
		ll here = prod;
		if (i) here = here * pref[i-1] % MOD;
		if (i != adj[cur].size() - 1) here = here * suff[i+1] % MOD;
		dfs(adj[cur][i], here);
	}

}

struct node {
	ll val;
	ll sum;
	ll flip;
} st[4 * N];

void up(ll i) {
	st[i].val = (st[rc].val + st[lc].val) % MOD;
	st[i].sum = (st[rc].sum + st[lc].sum) % MOD;
}

void down(ll i) {
	if (!st[i].flip) return;

	st[rc].val = (st[rc].sum - st[rc].val + MOD) % MOD;
	st[lc].val = (st[lc].sum - st[lc].val + MOD) % MOD;

	st[rc].flip = !st[rc].flip;
	st[lc].flip = !st[lc].flip;
	st[i].flip = 0;


}

void adjust(ll ind, ll val, ll on, ll i = 1, ll l = 0, ll r = N) { // should happen before range updates
	if (r <= l) return;
	if (r - l == 1 && l == ind) {
		// cout << val << endl;
		// assert(on <= 1);
		st[i].flip = 0;
		st[i].sum = val;
		st[i].val = st[i].sum * on;
		// cout << l << r << ' ' << st[i].val << endl;
		return;
	}
	// if (r - l == 1) return;
	// cout << l << r << endl;
	// cout << val << endl;

	ll m = (l + r) / 2;
	if (m > ind) adjust(ind, val, on, lc, l, m);
	else adjust(ind, val, on, rc, m, r);

	up(i);

	// cout << l << r << ' ' << st[i].val << ' ' << st[rc].val << ' ' << st[lc].val << endl;
}

void update(ll ul, ll ur, ll i = 1, ll l = 0, ll r = N) {
	if (r <= l) return;

	if (ul <= l && r <= ur) { // fully contained
		st[i].val = (st[i].sum - st[i].val + MOD) % MOD;
		st[i].flip = !st[i].flip;
		// cout << l << ' ' << r << ' ' << st[i].val << endl;
		return;
	}

	down(i);

	ll m = (l + r) / 2;
	if (m > ul) update(ul, ur, lc, l, m);
	if (m < ur) update(ul, ur, rc, m, r);

	up(i);
}

void init(int n_, int m_, vector<int> p_, vector<int> a) {
	n = n_;
	m = m_;
	FOR(i, 0, n + m) {

		p[i] = p_[i];
		if (i) adj[p[i]].pb(i);
	}
	calc_sub(0);
	dfs(0);

	FOR(i, n, n + m) {
		// cout << i << endl;
		adjust(i - n, contrib[i], a[i - n]);
	}
}

ll count_ways(int l, int r) {
	update(l - n, r - n+1);
	return st[1].val;
}


// int main() {
// 	// ll p[7] =  {-1, 0, 1, 2, 1, 1, 0};
// 	// ll a[4] = {1, 0, 1, 0};
// 	// init(3, 4, p, a);

// 	// // cout << st[1].val << endl;
// 	// cout << count_ways(3, 4) << endl;
// 	// cout << count_ways(4, 5) << endl;
// 	// cout << count_ways(3, 6) << endl;
// 	// FOR(i, n, n + m) cout << contrib[i] << endl;
// }

Compilation message (stderr)

circuit.cpp: In function 'void dfs(ll, ll)':
circuit.cpp:19:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (ll i = (a); i<b; i++)
......
   52 |  FOR(i, 0, adj[cur].size()) {
      |      ~~~~~~~~~~~~~~~~~~~~~              
circuit.cpp:52:2: note: in expansion of macro 'FOR'
   52 |  FOR(i, 0, adj[cur].size()) {
      |  ^~~
circuit.cpp:59:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if (i != adj[cur].size() - 1) suff[i] = suff[i + 1];
      |       ~~^~~~~~~~~~~~~~~~~~~~~~
circuit.cpp:19:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (ll i = (a); i<b; i++)
......
   64 |  FOR(i, 0, adj[cur].size()) {
      |      ~~~~~~~~~~~~~~~~~~~~~              
circuit.cpp:64:2: note: in expansion of macro 'FOR'
   64 |  FOR(i, 0, adj[cur].size()) {
      |  ^~~
circuit.cpp:67:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   if (i != adj[cur].size() - 1) here = here * suff[i+1] % MOD;
      |       ~~^~~~~~~~~~~~~~~~~~~~~~

• 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