oj.uz

Submission #835714

# Submission time Handle Problem Language Result Execution time Memory
835714 2023-08-23T17:57:30 Z APROHACK Digital Circuit (IOI22_circuit) C++17
7 / 100
 3000 ms 40784 KB 
#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int n, m;
vector<int>child[200001];
bool state[200001];
ll encen[200001][2]; // encendido y apagado
const ll MOD = 1000002022;
ll past[2002][2002];
void generate(int node);
int parent[200002];
bool casito = true;
ll aporte[200002];
ll prefix[200002];
ll T[200002];
ll ans = 0;
void precalc(int node){
	T[node] = 1;
	if(node >= n)return ;
	for(int i = 0 ; i < child[node].size() ; i ++){
		precalc(child[node][i]);
		T[node]  = T[node] * T[child[node][i]] % MOD;
	}	
	T[node] = T[node] * (ll)child[node].size() % MOD;
}
void calcPrefix(int node, ll acum){
	if(node >= n){
		aporte[node] = acum;	
		return ;
	}
	int hijo1 = child[node][0];
	int hijo2 = child[node][1];
	calcPrefix(hijo1, (acum * T[hijo2]) % MOD);
	calcPrefix(hijo2, (acum * T[hijo1]) % MOD);
}



void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	n = N;
	m = M;
	if( m != n+1 )casito = false;
	for(int i = 0 ; i < n+m ; i ++){
		if(P[i] != -1){
			child[P[i]].pb(i);
			if(P[i] != (i-1)/2)casito = false;
		}
		parent[i] = P[i];
	}
	int temp = m;
	while(temp != 1){
		if(temp % 2 == 1)casito = false;
		temp /= 2;
	}
	//assert(casito);
	for(int i = N ; i <= N+M ; i ++)state[i] = A[i-N];
	memset(past, -1, sizeof past);
	generate(0);
	ans = encen[0][0];
	precalc(0);

	calcPrefix(0, 1);
	prefix[0] = 0;
	for(int i = 1 ; i < N+M ; i ++){
		prefix[i] = (prefix[i-1] + aporte[i]) % MOD;	
	}
}

ll mem[2002][2002];
ll currentIt = -1 ;

void newDp(){
	currentIt++;
}
ll dp(int parent, ll i, int k){
	if(k < 0)return 0;
	if(i == child[parent].size() and k > 0)return 0;
	else if(i == child[parent].size()) return 1;
	if(past[i][k] == currentIt)return mem[i][k];
	past[i][k] = currentIt;
	return mem[i][k] = ((dp(parent, i+1, k-1) * encen[child[parent][i]][0] % MOD) + ((dp(parent, i+1, k) * encen[child[parent][i]][1])%MOD))%MOD;
}

void generate(int node){
	if(node >= n){
		if(state[node]){
			encen[node][0] = 1;
			encen[node][1] = 0;
		}else{
			encen[node][0] = 0;
			encen[node][1] = 1;

		}
		return ;
	}
	for(int i = 0 ; i < child[node].size() ; i ++){
		generate(child[node][i]);
	}
	newDp();
	ll enc = 0, inv = 0;
	for(ll i = 1 ; i <= child[node].size() ; i ++){
		enc += dp(node, 0, i) * i % MOD;
		enc %= MOD;
	}
	ll allWays = 1;
	for(int i = 0 ; i < child[node].size() ; i ++){
		allWays *= (encen[child[node][i]][0] + encen[child[node][i]][1])%MOD;
		allWays %= MOD;
	}
	allWays *= (ll)child[node].size();
	allWays %= MOD;
	encen[node][0] = enc;
	encen[node][1] = ((allWays - enc) + MOD) % MOD;
	//cout << "for node " << node << " there are " << encen[node][0] << ", " << encen[node][1] << "\n";
}
	

int count_ways(int L, int R) {
	for(int i = L ; i <= R ; i ++){
		state[i] = !state[i];
	}
	if(false  or ( L == R and casito and (n > 1000 or m > 1000) ) ){
		if(state[L])ans += aporte[L];
		else ans -= aporte[L];
		return ans;
	}
	else generate(0);
	return encen[0][0];
}

Compilation message

circuit.cpp: In function 'void precalc(int)':
circuit.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0 ; i < child[node].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'long long int dp(int, long long int, int)':
circuit.cpp:81:7: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  if(i == child[parent].size() and k > 0)return 0;
      |     ~~^~~~~~~~~~~~~~~~~~~~~~~
circuit.cpp:82:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  else if(i == child[parent].size()) return 1;
      |          ~~^~~~~~~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'void generate(int)':
circuit.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0 ; i < child[node].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
circuit.cpp:105:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(ll i = 1 ; i <= child[node].size() ; i ++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~~
circuit.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  for(int i = 0 ; i < child[node].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
circuit.cpp:104:14: warning: unused variable 'inv' [-Wunused-variable]
  104 |  ll enc = 0, inv = 0;
      |              ^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36328 KB Output is correct
2 Execution timed out 3078 ms 36340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36304 KB Output is correct
2 Correct 15 ms 36352 KB Output is correct
3 Correct 15 ms 36432 KB Output is correct
4 Correct 15 ms 36432 KB Output is correct
5 Correct 16 ms 36380 KB Output is correct
6 Correct 18 ms 36432 KB Output is correct
7 Correct 18 ms 36560 KB Output is correct
8 Correct 17 ms 36560 KB Output is correct
9 Correct 16 ms 36432 KB Output is correct
10 Correct 16 ms 36500 KB Output is correct
11 Correct 17 ms 36560 KB Output is correct
12 Correct 16 ms 36432 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36328 KB Output is correct
2 Execution timed out 3078 ms 36340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 494 ms 40784 KB 97th lines differ - on the 1st token, expected: '30382364', found: '1030384386'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 494 ms 40784 KB 97th lines differ - on the 1st token, expected: '30382364', found: '1030384386'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36304 KB Output is correct
2 Correct 15 ms 36352 KB Output is correct
3 Correct 15 ms 36432 KB Output is correct
4 Correct 15 ms 36432 KB Output is correct
5 Correct 16 ms 36380 KB Output is correct
6 Correct 18 ms 36432 KB Output is correct
7 Correct 18 ms 36560 KB Output is correct
8 Correct 17 ms 36560 KB Output is correct
9 Correct 16 ms 36432 KB Output is correct
10 Correct 16 ms 36500 KB Output is correct
11 Correct 17 ms 36560 KB Output is correct
12 Correct 16 ms 36432 KB Output is correct
13 Incorrect 494 ms 40784 KB 97th lines differ - on the 1st token, expected: '30382364', found: '1030384386'
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36328 KB Output is correct
2 Execution timed out 3078 ms 36340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 36328 KB Output is correct
2 Execution timed out 3078 ms 36340 KB Time limit exceeded
3 Halted 0 ms 0 KB -