oj.uz

Submission #835014

# Submission time Handle Problem Language Result Execution time Memory
835014 2023-08-23T05:52:05 Z pavement Digital Circuit (IOI22_circuit) C++17
18 / 100
 3000 ms 4148 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

using ll = long long;

const int MOD = (int)1e9 + 2022;
int N, M;
vector<int> A;
vector<vector<int> > adj;

void init(int N, int M, vector<int> P, vector<int> A) {
	::N = N;
	::M = M;
	::A = A;
	adj.resize(N + M);
	for (int i = 1; i < N + M; i++) {
		adj[P[i]].pb(i);
	}
}

int count_ways(int L, int R) {
	for (int i = L - N; i <= R - N; i++) {
		A[i] = !A[i];
	}
	
	vector<int> tot_mem(N + M, -1), dp_mem(N + M, -1);
	
	function<int(int)> tot = [&](int u) {
		if (tot_mem[u] != -1) {
			return tot_mem[u];
		}
		if (u >= N) {
			return tot_mem[u] = 1;
		}
		int ret = (int)(adj[u].size());
		for (auto v : adj[u]) {
			ret = ((ll)ret * (ll)tot(v)) % MOD;
		}
		return tot_mem[u] = ret;
	};
	
	function<int(int)> dp = [&](int u) {
		if (dp_mem[u] != -1) {
			return dp_mem[u];
		}
		if (u >= N) {
			return dp_mem[u] = A[u - N];
		}
		vector<int> sub_dp((int)adj[u].size() + 1, 0);
		sub_dp[0] = 1;
		for (auto v : adj[u]) {
			vector<int> new_sub_dp((int)adj[u].size() + 1);
			for (int i = 0; i <= (int)adj[u].size(); i++) {
				new_sub_dp[i] = ((i ? (ll)sub_dp[i - 1] * dp(v) : 0ll) % MOD + (ll)sub_dp[i] * ((ll)tot(v) - dp(v)) % MOD) % MOD;
				if (new_sub_dp[i] < 0) {
					new_sub_dp[i] += MOD;
				}
			}
			sub_dp = new_sub_dp;
		}
		int ret = 0;
		for (int i = 0; i <= (int)adj[u].size(); i++) {
			ret = (ret + (ll)i * sub_dp[i] % MOD) % MOD;
		}
		return dp_mem[u] = ret;
	};
	
	return dp(0);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 84 ms 340 KB Output is correct
4 Correct 99 ms 344 KB Output is correct
5 Correct 90 ms 344 KB Output is correct
6 Correct 86 ms 336 KB Output is correct
7 Correct 90 ms 348 KB Output is correct
8 Correct 88 ms 336 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 84 ms 340 KB Output is correct
4 Correct 99 ms 344 KB Output is correct
5 Correct 90 ms 344 KB Output is correct
6 Correct 86 ms 336 KB Output is correct
7 Correct 90 ms 348 KB Output is correct
8 Correct 88 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 1 ms 288 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 2 ms 592 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 4 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 86 ms 344 KB Output is correct
30 Correct 85 ms 464 KB Output is correct
31 Correct 1 ms 592 KB Output is correct
32 Correct 2 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 2 ms 336 KB Output is correct
35 Correct 18 ms 336 KB Output is correct
36 Correct 2 ms 592 KB Output is correct
37 Correct 88 ms 716 KB Output is correct
38 Correct 86 ms 592 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 5 ms 336 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 4148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 4148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Execution timed out 3071 ms 4148 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 84 ms 340 KB Output is correct
4 Correct 99 ms 344 KB Output is correct
5 Correct 90 ms 344 KB Output is correct
6 Correct 86 ms 336 KB Output is correct
7 Correct 90 ms 348 KB Output is correct
8 Correct 88 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 1 ms 288 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 2 ms 592 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 4 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 86 ms 344 KB Output is correct
30 Correct 85 ms 464 KB Output is correct
31 Correct 1 ms 592 KB Output is correct
32 Correct 2 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 2 ms 336 KB Output is correct
35 Correct 18 ms 336 KB Output is correct
36 Correct 2 ms 592 KB Output is correct
37 Correct 88 ms 716 KB Output is correct
38 Correct 86 ms 592 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 5 ms 336 KB Output is correct
43 Execution timed out 3071 ms 592 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 84 ms 340 KB Output is correct
4 Correct 99 ms 344 KB Output is correct
5 Correct 90 ms 344 KB Output is correct
6 Correct 86 ms 336 KB Output is correct
7 Correct 90 ms 348 KB Output is correct
8 Correct 88 ms 336 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 1 ms 288 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 2 ms 592 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 4 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 86 ms 344 KB Output is correct
30 Correct 85 ms 464 KB Output is correct
31 Correct 1 ms 592 KB Output is correct
32 Correct 2 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 2 ms 336 KB Output is correct
35 Correct 18 ms 336 KB Output is correct
36 Correct 2 ms 592 KB Output is correct
37 Correct 88 ms 716 KB Output is correct
38 Correct 86 ms 592 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 5 ms 336 KB Output is correct
43 Execution timed out 3071 ms 4148 KB Time limit exceeded
44 Halted 0 ms 0 KB -