oj.uz

Submission #802167

# Submission time Handle Problem Language Result Execution time Memory
802167 2023-08-02T10:37:15 Z MadokaMagicaFan Digital Circuit (IOI22_circuit) C++17
0 / 100
 578 ms 7368 KB 
#include "bits/stdc++.h"
#include "circuit.h"
using namespace std;
using ll = long long;
#define sz(v) ((int)(v).size())
#define pb push_back

const int N = 1e5;

ll md = 1e9+2022;
ll ans;
vector<int> adj[N+5];
vector<ll> t, st, c;
int n, m;

struct aint_lenes {
	int n;
	vector<ll> f;
	vector<int> lz;

	aint_lenes(int _n, vector<int> &a) {
		n = _n;
		f.assign(4*n, 0);
		lz.assign(4*n, 0);
		build(1, 0, n-1, a);
	}

	void build(int i, int l, int r, vector<int> &a) {
		if (l == r) {
			f[i] = a[l] % md;
			return;
		}
		int m = (l + r) >> 1;
		build(i<<1, l, m, a);
		build(i<<1|1, m+1, r, a);
		f[i] = (f[i<<1] + f[i<<1|1]) % md;
	}

	ll qry(int l, int r) {
		return qry(1, 0, n-1, l, r);
	}

	ll qry(int i, int l, int r, int tl, int tr) {
		if (r < tl || l > tr) return 0ll;
		lz[i] ^= 1;
		if (lz[i]) {
			lz[i] = 0;
			f[i] = (md-f[i])%md;
			if (l != r) {
				lz[i<<1] ^= 1;
				lz[i<<1|1] ^= 1;
			}
		}

		if (tl <= l && r <= tr) return f[i];
		int m = (l+r) >> 1;

		return (qry(i<<1, l, m, tl, tr) +
				qry(i<<1|1, m+1, r, tl, tr)) % md;
	}
};

aint_lenes *tr;

void
dfs1(int x) {
	if (x >= n) return;

	st[x] = 0;
	t[x] = sz(adj[x]);
	for (auto u : adj[x]) {
		dfs1(u);
		st[x] = (st[x] + t[u]) % md;
		t[x] = (t[x] * t[u]) % md;
	}
}

void
dfs2(int x, ll v) {
	if (x>=n) {
		c[x-n] = (c[x-n]*v) % md;
		return;
	}

	for (auto u : adj[x]) {
		dfs2(u, v);
		v = (v * t[u]) % md;
	}
}

void
init(int _n, int _m, vector<int> p, vector<int> a)
{
	n = _n; m = _m;
	t.assign(n+m, 1);
	st.assign(n+m, 1);
	c.assign(m, 1);
	for (int i = 1; i < n+m; ++i) {
		adj[p[i]].pb(i);
	}

	dfs1(0);
	dfs2(0, 1ll);
	for (int i = 0; i < n; ++i)
		reverse(adj[i].begin(), adj[i].end());
	dfs2(0, 1ll);

	vector<int> chn(m);

	for (int i = 0; i < m; ++i) {
		if (a[i]) {
			ans = (ans + c[i]) % md;
			chn[i] = c[i];
		} else {
			chn[i] = (md - c[i]) % md;
		}
	}

	tr = new aint_lenes(m, chn);
}

int
count_ways(int l, int r)
{
	l -= n; r -= n;
	ans = (ans + md - tr->qry(l, r)) % md;
	return ans;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB 2nd lines differ - on the 1st token, expected: '2', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB 2nd lines differ - on the 1st token, expected: '2', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB 2nd lines differ - on the 1st token, expected: '2', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 578 ms 7368 KB 4th lines differ - on the 1st token, expected: '469385826', found: '394586018'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 578 ms 7368 KB 4th lines differ - on the 1st token, expected: '469385826', found: '394586018'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB 2nd lines differ - on the 1st token, expected: '2', found: '0'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB 2nd lines differ - on the 1st token, expected: '2', found: '0'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB 2nd lines differ - on the 1st token, expected: '2', found: '0'
2 Halted 0 ms 0 KB -