oj.uz

Submission #1042479

# Submission time Handle Problem Language Result Execution time Memory
1042479 2024-08-03T05:17:06 Z Alihan_8 Digital Circuit (IOI22_circuit) C++17
11 / 100
 3000 ms 9304 KB 
#include "circuit.h"

#include <vector>

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define pb push_back
#define ln '\n'

const int Mod = 1000002022;

vector <int> a, fa;

vector <vector<int>> adj;

vector <ar<int,2>> dp;

int n, m;

template <class F, class S>
void add(F &x, const S &y){
	x = (x + 0LL + y) % Mod;
	
	if ( x < 0 ) x += Mod; 
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	a = A, n = N, m = M, fa = P;
	
	adj.resize(n + m);
	
	for ( int i = 1; i < n + m; i++ ){
		adj[P[i]].pb(i);
	}
	
	vector <int> s(n + m);
	
	dp.resize(n + m);
	
	auto dfs = [&](auto dfs, int u) -> void{
		if ( u >= n ){
			dp[u][1] = a[u - n];
			dp[u][0] = a[u - n] ^ 1;
			
			return;
		}
		
		for ( auto &v: adj[u] ){
			dfs(dfs, v);
			
			s[u] += 1;
		}
		
		vector <int> f(s[u] + 1);
		
		f[0] = 1;
		
		for ( auto &v: adj[u] ){
			vector <int> nxt(s[u] + 1);
			
			for ( int j = 0; j <= s[u]; j++ ){
				add(nxt[j], f[j] * 1LL * dp[v][0] % Mod);
				
				if ( j > 0 ){
					add(nxt[j], f[j - 1] * 1LL * dp[v][1] % Mod);
				}
			}
			
			swap(f, nxt);
		}
		
		for ( int i = 0; i <= s[u]; i++ ){
			add(dp[u][1], i * 1LL * f[i] % Mod);
			add(dp[u][0], (s[u] - i) * 1LL * f[i] % Mod);
		}
	};
	
	dfs(dfs, 0);
}

int count_ways(int L, int R) {
	L -= n, R -= n;
	
	for ( int i = L; i <= R; i++ ){
		a[i] ^= 1;
	}
	
	for ( int i = L; i <= R; i++ ){
		int u = i + n;
		
		while ( u != -1 ){
			if ( u >= n ){
				dp[u][1] = a[u - n];
				dp[u][0] = a[u - n] ^ 1;
			} else{		
				int s = (int)adj[u].size();
				
				vector <int> f(s + 1);
				
				f[0] = 1;
				
				for ( auto &v: adj[u] ){
					vector <int> nxt(s + 1);
					
					for ( int j = 0; j <= s; j++ ){
						add(nxt[j], f[j] * 1LL * dp[v][0] % Mod);
						
						if ( j > 0 ){
							add(nxt[j], f[j - 1] * 1LL * dp[v][1] % Mod);
						}
					}
					
					swap(f, nxt);
				}
				
				dp[u] = {0, 0};
				
				for ( int i = 0; i <= s; i++ ){
					add(dp[u][1], i * 1LL * f[i] % Mod);
					add(dp[u][0], (s - i) * 1LL * f[i] % Mod);
				}
			}
			
			u = fa[u];
		}
	}
		
	return dp[0][1];
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 412 KB Output is correct
3 Execution timed out 3056 ms 472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 95 ms 600 KB Output is correct
11 Correct 181 ms 600 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 412 KB Output is correct
3 Execution timed out 3056 ms 472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 4952 KB Output is correct
2 Correct 697 ms 9304 KB Output is correct
3 Correct 776 ms 9304 KB Output is correct
4 Correct 720 ms 9304 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 4952 KB Output is correct
2 Correct 697 ms 9304 KB Output is correct
3 Correct 776 ms 9304 KB Output is correct
4 Correct 720 ms 9304 KB Output is correct
5 Execution timed out 3037 ms 4952 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 95 ms 600 KB Output is correct
11 Correct 181 ms 600 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 505 ms 4952 KB Output is correct
14 Correct 697 ms 9304 KB Output is correct
15 Correct 776 ms 9304 KB Output is correct
16 Correct 720 ms 9304 KB Output is correct
17 Execution timed out 3037 ms 4952 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 412 KB Output is correct
3 Execution timed out 3056 ms 472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 412 KB Output is correct
3 Execution timed out 3056 ms 472 KB Time limit exceeded
4 Halted 0 ms 0 KB -