oj.uz

Submission #631650

# Submission time Handle Problem Language Result Execution time Memory
631650 2022-08-18T11:31:34 Z JustInCase Digital Circuit (IOI22_circuit) C++17
18 / 100
 3000 ms 4668 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <random>
#include <cstdlib>

#define debug(x) std::cout << #x << " " << (x) << '\n';
#define pb push_back
#define mp std::make_pair
#define remax(a, b) a = std::max((a), (b));
#define remin(a, b) a = std::min((a), (b));

#define countWays count_ways

const int32_t MOD = 1000002022;

struct Gate {
	int32_t value;
	int32_t waysOn, waysOff;
	std::vector<Gate*> children;
};

int32_t n, m;
std::vector<Gate> gates;

void init(int32_t _n, int32_t _m, std::vector<int32_t> p, std::vector<int32_t> a) {
	n = _n;
	m = _m;

	gates.resize(n + m);	

	for(int32_t i = 1; i < n + m; i++) {
		gates[p[i]].children.pb(&gates[i]);
		if(i >= n) {
			gates[i].value = a[i - n];
		}
	}
}

void computeDp() {
	for(int32_t i = n; i < n + m; i++) {
		gates[i].waysOn = (gates[i].value == 1);
		gates[i].waysOff = (gates[i].value == 0);
	}

	for(int32_t i = n - 1; i >= 0; i--) {
		gates[i].waysOn = 0;
		gates[i].waysOff = 0;

		int32_t k = gates[i].children.size();
		std::vector<std::vector<int32_t>> dp(k + 1, std::vector<int32_t>(k + 1));

		dp[0][0] = 1;
		for(int32_t pref = 1; pref <= k; pref++) {
			for(int32_t taken = 0; taken <= pref; taken++) {
				if(taken < pref) {
					int32_t waysNotTaken = ((int64_t) dp[pref - 1][taken] * gates[i].children[pref - 1]->waysOff) % MOD;
					dp[pref][taken] = ((int64_t) dp[pref][taken] + waysNotTaken) % MOD;
				}
				if(taken != 0) {
					int32_t waysTaken = ((int64_t) dp[pref - 1][taken - 1] * gates[i].children[pref - 1]->waysOn) % MOD;
					dp[pref][taken] = ((int64_t) dp[pref][taken] + waysTaken) % MOD;
				}
			}
		}

		//std::cout << i << ": ";
		for(int32_t j = 0; j <= k; j++) {
		//	std::cout << dp[k][j] << ", ";
			gates[i].waysOn = ((int64_t) gates[i].waysOn + (int64_t) dp[k][j] * j) % MOD;
			gates[i].waysOff = ((int64_t) gates[i].waysOff + (int64_t) dp[k][j] * (k - j)) % MOD;
		}
		//std::cout << "------>";

		//std::cout << gates[i].waysOn << ", " << gates[i].waysOff << '\n';
	}
}

int32_t countWays(int32_t l, int32_t r) {
	for(int32_t i = l; i <= r; i++) {
		gates[i].value = 1 - gates[i].value;
	}

	computeDp();

	return gates[0].waysOn;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 23 ms 4112 KB Output is correct
4 Correct 23 ms 4304 KB Output is correct
5 Correct 23 ms 4304 KB Output is correct
6 Correct 28 ms 4304 KB Output is correct
7 Correct 27 ms 4324 KB Output is correct
8 Correct 27 ms 4324 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 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 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 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 23 ms 4112 KB Output is correct
4 Correct 23 ms 4304 KB Output is correct
5 Correct 23 ms 4304 KB Output is correct
6 Correct 28 ms 4304 KB Output is correct
7 Correct 27 ms 4324 KB Output is correct
8 Correct 27 ms 4324 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 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 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 1 ms 336 KB Output is correct
25 Correct 2 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 28 ms 4340 KB Output is correct
30 Correct 27 ms 4324 KB Output is correct
31 Correct 4 ms 336 KB Output is correct
32 Correct 2 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 5 ms 552 KB Output is correct
36 Correct 1 ms 336 KB Output is correct
37 Correct 26 ms 4408 KB Output is correct
38 Correct 26 ms 4404 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 1 ms 336 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3019 ms 4668 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 3019 ms 4668 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 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Execution timed out 3019 ms 4668 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 23 ms 4112 KB Output is correct
4 Correct 23 ms 4304 KB Output is correct
5 Correct 23 ms 4304 KB Output is correct
6 Correct 28 ms 4304 KB Output is correct
7 Correct 27 ms 4324 KB Output is correct
8 Correct 27 ms 4324 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 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 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 1 ms 336 KB Output is correct
25 Correct 2 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 28 ms 4340 KB Output is correct
30 Correct 27 ms 4324 KB Output is correct
31 Correct 4 ms 336 KB Output is correct
32 Correct 2 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 5 ms 552 KB Output is correct
36 Correct 1 ms 336 KB Output is correct
37 Correct 26 ms 4408 KB Output is correct
38 Correct 26 ms 4404 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 1 ms 336 KB Output is correct
43 Execution timed out 3069 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 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 23 ms 4112 KB Output is correct
4 Correct 23 ms 4304 KB Output is correct
5 Correct 23 ms 4304 KB Output is correct
6 Correct 28 ms 4304 KB Output is correct
7 Correct 27 ms 4324 KB Output is correct
8 Correct 27 ms 4324 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 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 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 1 ms 336 KB Output is correct
25 Correct 2 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 28 ms 4340 KB Output is correct
30 Correct 27 ms 4324 KB Output is correct
31 Correct 4 ms 336 KB Output is correct
32 Correct 2 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 5 ms 552 KB Output is correct
36 Correct 1 ms 336 KB Output is correct
37 Correct 26 ms 4408 KB Output is correct
38 Correct 26 ms 4404 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 1 ms 336 KB Output is correct
43 Execution timed out 3019 ms 4668 KB Time limit exceeded
44 Halted 0 ms 0 KB -