Submission #667270

#	Time	Username	Problem	Language	Result	Execution time	Memory
667270		flappybird	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1125 ms	48880 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000002022ll
#define MAX 201010

int N, M;
vector<int> adj[MAX], prt;
vector<ll> psum[MAX], ssum[MAX];
ll A[MAX];
ll ma[MAX];
ll mulall[MAX];
vector<int> ison;

ll f(ll& a) { a %= MOD, a += MOD, a %= MOD; return a; }

struct segtree {
	vector<ll> tree, sum;
	vector<int> lazy;
	void init(int s, int e, int ind) {
		if (s == e) {
			sum[ind] = mulall[s];
			if (ison[s]) tree[ind] = mulall[s];
			return;
		}
		int m = (s + e) >> 1;
		init(s, m, ind * 2);
		init(m + 1, e, ind * 2 + 1);
		sum[ind] = sum[ind * 2] + sum[ind * 2 + 1];
		f(sum[ind]);
		tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
		f(tree[ind]);
	}
	segtree(int N = 0) {
		tree.resize(N * 4);
		lazy.resize(N * 4);
		sum.resize(N * 4);
	}
	void prop(int ind) {
		if (lazy[ind]) {
			for (auto c : { ind * 2, ind * 2 + 1 }) tree[c] = sum[c] - tree[c], f(tree[c]), lazy[c] ^= 1;
			lazy[ind] = 0;
		}
	}
	void upd(int s, int e, int l, int r, int ind = 1) {
		if (e < l || r < s) return;
		if (s != e) prop(ind);
		if (l <= s && e <= r) {
			tree[ind] = sum[ind] - tree[ind];
			f(tree[ind]);
			lazy[ind] ^= 1;
			return;
		}
		int m = (s + e) >> 1;
		upd(s, m, l, r, ind * 2);
		upd(m + 1, e, l, r, ind * 2 + 1);
		tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
		f(tree[ind]);
	}
	ll get() { return tree[1]; }
};

void dfs(int x) {
	A[x] = 1;
	ma[x] = 1;
	if (x >= N) {
		return;
	}
	psum[x].resize(adj[x].size());
	ssum[x].resize(adj[x].size());
	int i;
	for (i = 0; i < adj[x].size(); i++) {
		int v = adj[x][i];
		dfs(v);
		psum[x][i] = ssum[x][i] = A[v];
		A[x] *= A[v];
		A[x] %= MOD;
	}
	A[x] *= adj[x].size();
	f(A[x]);
	int c = adj[x].size();
	for (i = 1; i < c; i++) psum[x][i] *= psum[x][i - 1], f(psum[x][i]);
	for (i = c - 2; i >= 0; i--) ssum[x][i] *= ssum[x][i + 1], f(ssum[x][i]);
	for (i = 0; i < c; i++) {
		ll mul = 1;
		if (i > 0) mul *= psum[x][i - 1], f(mul);
		if (i < c - 1) mul *= ssum[x][i + 1], f(mul);
		ma[adj[x][i]] *= mul;
		f(ma[adj[x][i]]);
	}
}

void calc(int x, ll d) {
	d *= ma[x];
	d %= MOD;
	if (x >= N) mulall[x - N + 1] = d;
	for (auto v : adj[x]) calc(v, d);
}

segtree seg;

void init(int _N, int _M, std::vector<int> _P, std::vector<int> A) {
	prt = _P;
	N = _N;
	M = _M;
	for (int i = 1; i < N + M; i++) adj[prt[i]].push_back(i);
	dfs(0);
	calc(0, 1);
	ison = A;
	ison.insert(ison.begin(), 0);
	seg = segtree(M);
	seg.init(1, M, 1);
}

int count_ways(int L, int R) {
	L -= N - 1;
	R -= N - 1;
	seg.upd(1, M, L, R);
	return seg.get();
}

Compilation message (stderr)

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