oj.uz

답안 #1042479

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042479 2024-08-03T05:17:06 Z Alihan_8 디지털 회로 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -