oj.uz

Submission #748841

# Submission time Handle Problem Language Result Execution time Memory
748841 2023-05-27T05:07:46 Z QwertyPi Digital Circuit (IOI22_circuit) C++17
2 / 100
 728 ms 9112 KB 
#include "circuit.h"
#include <bits/stdc++.h>
#define int long long
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];
int N, M;

int norm(int x){
	return (x % MOD + MOD) % MOD;
}

namespace SegTree{
	int s[N_MAX << 2], t[N_MAX << 2], lz[N_MAX << 2];
	void push(int v){
		if(lz[v]){
			t[v * 2 + 1] = norm(s[v * 2 + 1] - t[v * 2 + 1]);
			t[v * 2 + 2] = norm(s[v * 2 + 2] - t[v * 2 + 2]);
			lz[v * 2 + 1] ^= 1;
			lz[v * 2 + 2] ^= 1;
			lz[v] = 0;
		}
	}
	void build(int v, int l, int r){
		if(l == r){
			s[v] = g[l];
			t[v] = g[l] * ac[l];
		}else{
			int m = (l + r) / 2;
			build(v * 2 + 1, l, m);
			build(v * 2 + 2, m + 1, r);
			s[v] = s[v * 2 + 1] + s[v * 2 + 2];
			t[v] = t[v * 2 + 1] + t[v * 2 + 2];
		}
	}
	void toggle(int ql, int qr, int v, int l, int r){
		if(qr < l || r < ql) return;
		if(ql <= l && r <= qr){
			t[v] = norm(s[v] - t[v]);
			lz[v] ^= 1;
			return;
		}
		push(v);
		int m = (l + r) / 2;
		toggle(ql, qr, v * 2 + 1, l, m);
		toggle(ql, qr, v * 2 + 2, m + 1, r);
		t[v] = t[v * 2 + 1] + t[v * 2 + 2];
	}
	int query(){
		return t[0];
	}
};
void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) {
	::N = N; ::M = M;
	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];
	}
	
	SegTree::build(0, N, N + M - 1);
}

int32_t count_ways(int32_t L, int32_t R) {
	SegTree::toggle(L, R, 0, N, N + M - 1);
	return SegTree::query();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 4 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 4 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 4 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 4 ms 5072 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5072 KB Output is correct
9 Correct 3 ms 4944 KB Output is correct
10 Incorrect 3 ms 5072 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11 Halted 0 ms 0 KB -