oj.uz

Submission #1024485

# Submission time Handle Problem Language Result Execution time Memory
1024485 2024-07-16T05:49:52 Z vjudge1 Digital Circuit (IOI22_circuit) C++17
16 / 100
 928 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 2 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 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 1 ms 10584 KB Output is correct
4 Correct 1 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 2 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 504 ms 12632 KB Output is correct
2 Correct 787 ms 14680 KB Output is correct
3 Correct 736 ms 14680 KB Output is correct
4 Correct 742 ms 14680 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 12632 KB Output is correct
2 Correct 787 ms 14680 KB Output is correct
3 Correct 736 ms 14680 KB Output is correct
4 Correct 742 ms 14680 KB Output is correct
5 Correct 656 ms 12632 KB Output is correct
6 Correct 918 ms 14680 KB Output is correct
7 Correct 928 ms 14556 KB Output is correct
8 Correct 758 ms 14680 KB Output is correct
9 Correct 395 ms 10584 KB Output is correct
10 Correct 767 ms 10840 KB Output is correct
11 Correct 753 ms 10840 KB Output is correct
12 Correct 678 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 1 ms 10584 KB Output is correct
4 Correct 1 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 2 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 2 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 -