oj.uz

Submission #645286

# Submission time Handle Problem Language Result Execution time Memory
645286 2022-09-26T16:01:27 Z dozer Digital Circuit (IOI22_circuit) C++17
50 / 100
 1362 ms 2097152 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sp " "
#define endl "\n"
#define L(node) node * 2
#define R(node) node * 2 + 1
#define ll long long

const int modulo = 1000002022;

vector<int> adj[2000005];
int sz[400005], arr[400005], tree[2000005 * 4], tree2[2000005 * 4], lazy[2000005 * 4];
int n, m;


ll add(ll a, ll b)
{
	return (a + b) % modulo;
}

ll subs(ll a, ll b)
{
	return (((a - b) % modulo) + modulo) % modulo;
}

ll mul(ll a, ll b)
{
	return (a * b) % modulo;
}

int dfs(int node, int root)
{
	if (adj[node].empty()) return sz[node] = 1;
	sz[node] = 2;
	for (auto i : adj[node])
		sz[node] = mul(sz[node], dfs(i, node));
	return sz[node];
}

void dfs2(int node, int root, int val)
{
	arr[node] = val;
	if (adj[node].empty())
	{
		return;
	}
	dfs2(adj[node][1], node, mul(val, sz[adj[node][0]]));
	dfs2(adj[node][0], node, mul(val, sz[adj[node][1]]));
}	

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = arr[l - 1];
		return;
	}
	int mid = (l + r) / 2;
	build(L(node), l, mid);
	build(R(node), mid + 1, r);
	tree[node] = add(tree[L(node)], tree[R(node)]);
}


void push(int node, int l, int r)
{
	if (lazy[node] == 0) return;
	tree2[node] = subs(tree[node], tree2[node]);
	lazy[node] = 0;
	if (l == r)
		return;
	lazy[L(node)] ^= 1;
	lazy[R(node)] ^= 1;
}

void update(int node, int l, int r, int sl, int sr)
{
	push(node, l, r);
	if (l > r || l > sr || r < sl) return;
	int mid = (l + r) / 2;
	if (l >= sl && r <= sr)
	{
		lazy[node] ^= 1;
		push(node, l, r);
		return;
	}
	push(node, l, r);
	update(L(node), l, mid, sl, sr);
	update(R(node), mid + 1, r, sl, sr);
	tree2[node] = add(tree2[L(node)], tree2[R(node)]);
}

int sum(int node, int l, int r, int sl, int sr)
{
	push(node, l, r);
	if (l > r || l > sr || r < sl) return 0;
	if (l >= sl && r <= sr) return tree2[node];
	int mid = (l + r) / 2;
	return add(sum(L(node), l, mid, sl, sr), sum(R(node), mid + 1, r, sl, sr));
}


void init(int N, int M, vector<int> P, vector<int> A)
{
	n = N, m = M;
	for (int i = 1; i < N + M; i++)
		adj[P[i]].pb(i);
	int tmp = dfs(0, -1);
	dfs2(0, -1, 1);
	build(1, 1, N + M);
	for (int i = 0; i < M; i++)
		if (A[i]) update(1, 1, N + M, N + i + 1, N + i + 1);
}

int count_ways(int L, int R)
{
	update(1, 1, n + m, L + 1, R + 1);
	return sum(1, 1, n + m, 1, n + m);
}

Compilation message

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:112:6: warning: unused variable 'tmp' [-Wunused-variable]
  112 |  int tmp = dfs(0, -1);
      |      ^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47196 KB Output is correct
2 Runtime error 1362 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47184 KB Output is correct
2 Correct 25 ms 47316 KB Output is correct
3 Correct 27 ms 47304 KB Output is correct
4 Correct 25 ms 47312 KB Output is correct
5 Correct 30 ms 47340 KB Output is correct
6 Correct 33 ms 47312 KB Output is correct
7 Correct 28 ms 47312 KB Output is correct
8 Correct 26 ms 47312 KB Output is correct
9 Correct 26 ms 47304 KB Output is correct
10 Correct 29 ms 47408 KB Output is correct
11 Correct 26 ms 47440 KB Output is correct
12 Correct 26 ms 47436 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47196 KB Output is correct
2 Runtime error 1362 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 50480 KB Output is correct
2 Correct 944 ms 53704 KB Output is correct
3 Correct 949 ms 53636 KB Output is correct
4 Correct 1093 ms 52988 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 50480 KB Output is correct
2 Correct 944 ms 53704 KB Output is correct
3 Correct 949 ms 53636 KB Output is correct
4 Correct 1093 ms 52988 KB Output is correct
5 Correct 758 ms 50484 KB Output is correct
6 Correct 1069 ms 53708 KB Output is correct
7 Correct 1115 ms 53704 KB Output is correct
8 Correct 1155 ms 53704 KB Output is correct
9 Correct 512 ms 47440 KB Output is correct
10 Correct 908 ms 47696 KB Output is correct
11 Correct 784 ms 47688 KB Output is correct
12 Correct 1000 ms 47740 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47184 KB Output is correct
2 Correct 25 ms 47316 KB Output is correct
3 Correct 27 ms 47304 KB Output is correct
4 Correct 25 ms 47312 KB Output is correct
5 Correct 30 ms 47340 KB Output is correct
6 Correct 33 ms 47312 KB Output is correct
7 Correct 28 ms 47312 KB Output is correct
8 Correct 26 ms 47312 KB Output is correct
9 Correct 26 ms 47304 KB Output is correct
10 Correct 29 ms 47408 KB Output is correct
11 Correct 26 ms 47440 KB Output is correct
12 Correct 26 ms 47436 KB Output is correct
13 Correct 785 ms 50480 KB Output is correct
14 Correct 944 ms 53704 KB Output is correct
15 Correct 949 ms 53636 KB Output is correct
16 Correct 1093 ms 52988 KB Output is correct
17 Correct 758 ms 50484 KB Output is correct
18 Correct 1069 ms 53708 KB Output is correct
19 Correct 1115 ms 53704 KB Output is correct
20 Correct 1155 ms 53704 KB Output is correct
21 Correct 512 ms 47440 KB Output is correct
22 Correct 908 ms 47696 KB Output is correct
23 Correct 784 ms 47688 KB Output is correct
24 Correct 1000 ms 47740 KB Output is correct
25 Correct 1022 ms 58000 KB Output is correct
26 Correct 1167 ms 58232 KB Output is correct
27 Correct 809 ms 58140 KB Output is correct
28 Correct 681 ms 58272 KB Output is correct
29 Correct 1060 ms 64456 KB Output is correct
30 Correct 1095 ms 64444 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47196 KB Output is correct
2 Runtime error 1362 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47196 KB Output is correct
2 Runtime error 1362 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -