oj.uz

Submission #1024677

# Submission time Handle Problem Language Result Execution time Memory
1024677 2024-07-16T09:08:32 Z vjudge1 Digital Circuit (IOI22_circuit) C++17
16 / 100
 868 ms 14680 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 10676 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 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10836 KB Output is correct
6 Incorrect 2 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 10676 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 530 ms 12636 KB Output is correct
2 Correct 786 ms 14552 KB Output is correct
3 Correct 856 ms 14672 KB Output is correct
4 Correct 794 ms 14680 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 12636 KB Output is correct
2 Correct 786 ms 14552 KB Output is correct
3 Correct 856 ms 14672 KB Output is correct
4 Correct 794 ms 14680 KB Output is correct
5 Correct 687 ms 12744 KB Output is correct
6 Correct 859 ms 14680 KB Output is correct
7 Correct 868 ms 14680 KB Output is correct
8 Correct 810 ms 14672 KB Output is correct
9 Correct 315 ms 10584 KB Output is correct
10 Correct 657 ms 10840 KB Output is correct
11 Correct 800 ms 10840 KB Output is correct
12 Correct 745 ms 10840 KB Output is correct

Subtask #6
0 / 27.0

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