oj.uz

Submission #1024482

# Submission time Handle Problem Language Result Execution time Memory
1024482 2024-07-16T05:49:05 Z Issa Digital Circuit (IOI22_circuit) C++17
16 / 100
 844 ms 14792 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int, int> pii;

const int MOD = 1000002022;
const int maxn = 2e5 + 100;

int n, k;
int p[maxn];
vector<int> g[maxn];
int a[maxn];
ll dp[2][maxn * 4];
int t[maxn * 4];
ll d[maxn];

void calc(int v){
	fill(d, d + g[v].size() + 1, 0);
	d[0] = 1; dp[1][v] = dp[0][v] = 0;
	for(int to: g[v]){
		for(int cnt = g[v].size(); cnt >= 0; cnt--){
			d[cnt] = d[cnt] * dp[0][to] % MOD;
			if(cnt) d[cnt] = (d[cnt] + d[cnt-1] * dp[1][to]) % MOD;
		}
	}
	for(int cnt = 0; cnt <= g[v].size(); cnt++){
		dp[1][v] = (dp[1][v] + d[cnt] * cnt) % MOD;
		dp[0][v] = (dp[0][v] + d[cnt] * (g[v].size() - cnt)) % MOD;
	}
}

void pre(int v){
	t[v] ^= 1;
	swap(dp[0][v], dp[1][v]);
}

void push(int v, int tl, int tr){
	if(tl == tr || !t[v]) return;
	pre(v<<1); pre(v<<1|1); t[v] = 0;
}

void upd(int l, int r, int v = 1, int tl = 1 + k, int tr = n){
	push(v, tl, tr);
	if(tl > r || tr < l) return;
	if(l <= tl && tr <= r) pre(v);
	else{
		int mid = (tl + tr) >> 1;
		upd(l, r, v<<1, tl, mid);
		upd(l, r, v<<1|1, mid+1, tr);
		calc(v);
	}
}

void updp(int i, int v = 1, int tl = k + 1, int tr = n){
	if(tl == tr) swap(dp[0][v], dp[1][v]);
	else{
		int mid = (tl + tr) >> 1;
		if(i <= mid) updp(i, v<<1, tl, mid);
		else updp(i, v<<1|1, mid+1, tr);
		calc(v);
	}
}

void init(int N, int M, std::vector<int> P, std::vector<int> A){
	n = N + M; k = N;
	for(int i = 1; i <= n; i++){
		p[i] = P[i-1]; p[i]++;
		g[p[i]].push_back(i);
	}
	for(int i = k + 1; i <= n; i++){
		a[i] = A[i - k - 1];
		dp[a[i]][i] = 1;
		dp[a[i]^1][i] = 0;
	}
	for(int i = k; i > 0; i--){
		calc(i);
	}
}

int count_ways(int L, int R){
	upd(L + 1, R + 1);
	return dp[1][1];
}

Compilation message

circuit.cpp: In function 'void calc(int)':
circuit.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int cnt = 0; cnt <= g[v].size(); cnt++){
      |                   ~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10584 KB Output is correct
3 Correct 1 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 1 ms 10584 KB Output is correct
6 Incorrect 1 ms 10584 KB 1st lines differ - on the 1st token, expected: '706880838', found: '445274432'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 12628 KB Output is correct
2 Correct 760 ms 14680 KB Output is correct
3 Correct 731 ms 14676 KB Output is correct
4 Correct 691 ms 14680 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 12628 KB Output is correct
2 Correct 760 ms 14680 KB Output is correct
3 Correct 731 ms 14676 KB Output is correct
4 Correct 691 ms 14680 KB Output is correct
5 Correct 642 ms 12632 KB Output is correct
6 Correct 844 ms 14680 KB Output is correct
7 Correct 815 ms 14792 KB Output is correct
8 Correct 799 ms 14680 KB Output is correct
9 Correct 359 ms 10584 KB Output is correct
10 Correct 733 ms 10840 KB Output is correct
11 Correct 756 ms 10840 KB Output is correct
12 Correct 675 ms 10840 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10584 KB Output is correct
3 Correct 1 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 1 ms 10584 KB Output is correct
6 Incorrect 1 ms 10584 KB 1st lines differ - on the 1st token, expected: '706880838', found: '445274432'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Incorrect 20 ms 10740 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 10584 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Incorrect 20 ms 10740 KB 1st lines differ - on the 1st token, expected: '509', found: '0'
4 Halted 0 ms 0 KB -