oj.uz

Submission #680911

# Submission time Handle Problem Language Result Execution time Memory
680911 2023-01-12T02:57:14 Z Justin1 Digital Circuit (IOI22_circuit) C++17
4 / 100
 969 ms 11144 KB 
//0 - n-1 = non leaf, n - m-1 = leaf

#include "circuit.h"
#include <bits/stdc++.h>
// #define signed int
#define int long long
using namespace std;

const int mod = 1e9 + 2022;
int n, m, k, x, y, z;
int dp[200005][2];
vector<signed> par, gph[200005];

void dfs(int id) {
	int L = -1, R = -1;
	if (gph[id].size()) L = gph[id][0], R = gph[id][1];
	else return;
	dfs(L), dfs(R);
	dp[id][0] = dp[L][1] * dp[R][0] + dp[L][0] * dp[R][1] + 2 * dp[L][0] * dp[R][0];
	dp[id][1] = dp[L][1] * dp[R][0] + dp[L][0] * dp[R][1] + 2 * dp[L][1] * dp[R][1];
	dp[id][0] %= mod;
	dp[id][1] %= mod;
}

void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
	n = N, m = M, par = P;
	for (int i = 1; i < n + m; i++) gph[P[i]].push_back(i);
	for (int i = n; i < n + m; i++) dp[i][A[i-n]] = 1;
	dfs(0);
}

signed count_ways(signed L, signed R) {
	swap(dp[L][0], dp[R][1]);
	int id = par[L];
	while (id != -1) {
		int L = gph[id][0], R = gph[id][1];
		dp[id][0] = dp[L][1] * dp[R][0] + dp[L][0] * dp[R][1] + 2 * dp[L][0] * dp[R][0];
		dp[id][1] = dp[L][1] * dp[R][0] + dp[L][0] * dp[R][1] + 2 * dp[L][1] * dp[R][1];
		dp[id][0] %= mod;
		dp[id][1] %= mod;
		id = par[id];
	}
	return dp[0][1];
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 8060 KB Output is correct
2 Correct 961 ms 11132 KB Output is correct
3 Correct 948 ms 11136 KB Output is correct
4 Correct 969 ms 11144 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 8060 KB Output is correct
2 Correct 961 ms 11132 KB Output is correct
3 Correct 948 ms 11136 KB Output is correct
4 Correct 969 ms 11144 KB Output is correct
5 Incorrect 665 ms 8060 KB 1st lines differ - on the 1st token, expected: '105182172', found: '40177750'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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