oj.uz

Submission #835010

# Submission time Handle Problem Language Result Execution time Memory
835010 2023-08-23T05:36:41 Z pavement Digital Circuit (IOI22_circuit) C++17
7 / 100
 3000 ms 4108 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];
		}
		int ret = 0;
		for (int bm = 0; bm < (1 << (int)adj[u].size()); bm++) {
			int cur = __builtin_popcount(bm);
			for (int i = 0; i < (int)adj[u].size(); i++) {
				int tmp = (bm & (1 << i) ? dp(adj[u][i]) : tot(adj[u][i]) - dp(adj[u][i])) % MOD;
				if (tmp < 0) {
					tmp += MOD;
				}
				cur = (ll)cur * (ll)tmp % MOD;
			}
			ret = (ret + cur) % MOD;
		}
		return dp_mem[u] = ret;
	};
	
	return dp(0);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 248 ms 208 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.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 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 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 248 ms 208 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 4108 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 3080 ms 4108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.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 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 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Execution timed out 3080 ms 4108 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 0 ms 208 KB Output is correct
3 Incorrect 248 ms 208 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 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 0 ms 208 KB Output is correct
3 Incorrect 248 ms 208 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -