oj.uz

Submission #681576

# Submission time Handle Problem Language Result Execution time Memory
681576 2023-01-13T11:36:50 Z Justin1 Digital Circuit (IOI22_circuit) C++17
0 / 100
 564 ms 10876 KB 
#include "circuit.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int mod = 1e9 + 2022;
int n, m, k, x, y, z;
int val[200005], cont[200005], cur[200005];
int seg[1'000'005], lzy[1'000'005], ps[200005];
vector<signed> par, gph[200005];

void dfs(int id) {
	val[id] = id >= n ? 1 : gph[id].size();
	for (auto i : gph[id]) dfs(i), val[id] = val[id] * val[i] % mod;
}

void dfs2(int id, int cur) {
	if (id >= n) cont[id - n + 1] = cur;
	int post[gph[id].size()+2], pre = 1;
	post[gph[id].size()+1] = 1;
	for (int i = gph[id].size(); i >= 1; i--) post[i] = post[i+1] * val[gph[id][i-1]] % mod;
	for (int i = 1; i <= gph[id].size(); i++) {
		dfs2(gph[id][i-1], cur * pre % mod * post[i+1] % mod);
		pre = pre * val[gph[id][i-1]] % mod;
	}
}

void push(int id, int l, int r) {
	if (!lzy[id]) return;
	int mid = (l + r) / 2;
	seg[id * 2] = ps[mid] - ps[l-1] - seg[id * 2];
	seg[id * 2 + 1] = ps[r] - ps[mid] - seg[id * 2 + 1];
	lzy[2 * id] = lzy[2 * id + 1] = !(lzy[id] = 0);
}

void upd(int t1, int t2, int id = 1, int l = 1, int r = 100000) {
	push(id, l, r);
	if (r < t1 || t2 < l) return;
	if (t1 <= l && r <= t2) {
		seg[id] = ps[r] - ps[l-1] - seg[id];
		lzy[id] ^= 1;
		return;
	}
	int mid = (l + r) / 2;
	upd(t1, t2, id * 2, l, mid), upd(t1, t2, id * 2 + 1, mid + 1, r);
	seg[id] = seg[id * 2] + seg[id * 2 + 1];
}

void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
	n = N, m = M, par = P;
	for (int i = 1; i < n + m; i++) gph[P[i]].push_back(i);
	for (int i = n; i < n + m; i++) cur[i] = A[i-n];
	dfs(0);
	dfs2(0, 1);
	for (int i = 1; i <= m; i++) ps[i] = (ps[i-1] + cont[i]) % mod;
	for (int i = 1; i <= m; i++) if (A[i-1]) upd(i, i);
}
 
signed count_ways(signed L, signed R) {
	upd(L - n + 1, R - n + 1);
	return seg[1];
}

Compilation message

circuit.cpp: In function 'void dfs2(long long int, long long int)':
circuit.cpp:22:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 1; i <= gph[id].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 3 ms 5080 KB Output is correct
3 Incorrect 3 ms 5200 KB 5th lines differ - on the 1st token, expected: '481', found: '497'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 3 ms 5080 KB Output is correct
3 Incorrect 3 ms 5200 KB 5th lines differ - on the 1st token, expected: '481', found: '497'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 27.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 3 ms 5080 KB Output is correct
3 Incorrect 3 ms 5200 KB 5th lines differ - on the 1st token, expected: '481', found: '497'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 3 ms 5080 KB Output is correct
3 Incorrect 3 ms 5200 KB 5th lines differ - on the 1st token, expected: '481', found: '497'
4 Halted 0 ms 0 KB -