oj.uz

Submission #748835

# Submission time Handle Problem Language Result Execution time Memory
748835 2023-05-27T04:47:47 Z QwertyPi Digital Circuit (IOI22_circuit) C++17
0 / 100
 622 ms 7420 KB 
#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 2e5 + 11;
const int MOD = 1000002022;
vector<int> G[N_MAX];
int f[N_MAX], g[N_MAX];

void dfsU(int v){
	f[v] = G[v].empty() ? 1 : G[v].size();
	for(auto u : G[v]){
		dfsU(u);
		f[v] = (f[v] * f[u]) % MOD;
	}
}

int a[N_MAX << 2];
void upd(int pos, int val, int v, int l, int r){
	if(l == r) a[v] = val;
	else {
		int m = (l + r) / 2;
		if(pos <= m){
			upd(pos, val, v * 2 + 1, l, m);
		}else{
			upd(pos, val, v * 2 + 2, m + 1, r);
		}
		a[v] = a[v * 2 + 1] * a[v * 2 + 2] % MOD;
	}
}

int qry(int ql, int qr, int v, int l, int r){
	if(qr < l || r < ql) return 1;
	if(ql <= l && r <= qr) return a[v];
	int m = (l + r) / 2;
	
	int qx = qry(ql, qr, v * 2 + 1, l, m);
	int qy = qry(ql, qr, v * 2 + 2, m + 1, r);
	return qx * qy % MOD;
}

int qry_except(int x, int V){
	int qx = qry(0, x - 1, 0, 0, V - 1);
	int qy = qry(x + 1, V - 1, 0, 0, V - 1);
	return qx * qy % MOD;
}

void dfsD(int v){
	
	int V = G[v].size();
	for(int i = 0; i < V; i++){
		int u = G[v][i];
		upd(i, f[u], 0, 0, V - 1);
	}
	for(int i = 0; i < V; i++){
		int u = G[v][i];
		g[u] = g[v] * qry_except(i, V) % MOD;
	}
	for(int i = 0; i < V; i++){
		dfsD(G[v][i]);
	} 
}

int ac[N_MAX];
void init(int N, int M, vector<int> P, vector<int> A) {
	for(int i = 1; i < N + M; i++){
		G[P[i]].push_back(i);
	}
	dfsU(0);
	g[0] = 1; dfsD(0);
	
	for(int i = N; i < N + M; i++){
		ac[i] = A[i - N];
	}
}

int count_ways(int L, int R) {
	for(int i = L; i <= R; i++){
		ac[i] = !ac[i];
	}
	
	int ans = 0;
	for(int i = L; i <= R; i++){
		ans += ac[i] * g[i];
		ans %= MOD;
	}
	return ans;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4976 KB 2nd lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4944 KB 2nd lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4976 KB 2nd lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 622 ms 7420 KB 1st lines differ - on the 1st token, expected: '431985922', found: '504795968'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 622 ms 7420 KB 1st lines differ - on the 1st token, expected: '431985922', found: '504795968'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4944 KB 2nd lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4976 KB 2nd lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4976 KB 2nd lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -