oj.uz

Submission #1030885

# Submission time Handle Problem Language Result Execution time Memory
1030885 2024-07-22T11:21:47 Z 0npata Digital Circuit (IOI22_circuit) C++17
52 / 100
 740 ms 32080 KB 
#include "circuit.h"
#include<bits/stdc++.h>

using namespace std;

#define vec vector
#define int long long
#define arr array

const int MX = 200'005;

vec<int32_t> a;
vec<int> tree[MX];
int tot[MX];
int n, m;
const int MXM = 100'005;
const int MOD = 1'000'002'022;
int contr[MXM];

struct SegLazy {
	bool flip = false;

	SegLazy merge(SegLazy other) {
		return {flip ^ other.flip};
	}
};

struct SegNode {
	arr<int, 2> sums = {0, 0};

	SegNode merge(SegNode other) {
		return {{sums[0]+other.sums[0], sums[1]+other.sums[1]}};
	}

	SegNode upd(SegLazy lazy) {
		if(lazy.flip) {
			return {{sums[1], sums[0]}};
		}
		else {
			return {{sums[0], sums[1]}};
		}
	}
};


struct SegTree {
	int n;
	vec<SegNode> data;
	vec<SegLazy> lazy;

	SegTree(int in) {
		n = 1;
		while(n < in) n *= 2;
		data = vec<SegNode>(n*2);
		lazy = vec<SegLazy>(n*2);
	}

	void pull(int i) {
		data[i] = data[i*2].merge(data[i*2+1]);
	}

	void set(int i, SegNode val) {
		i += n;
		data[i] = val;
		while(i > 1) {
			i /= 2;
			pull(i);
		}
	}

	void push(int i) {
		data[i] = data[i].upd(lazy[i]);
		if(i*2 >= n*2) {
			lazy[i] = {};
			return;
		}
		lazy[i*2] = lazy[i*2].merge(lazy[i]);
		lazy[i*2+1] = lazy[i*2+1].merge(lazy[i]);
		lazy[i] = {};
	}


	void upd(int l, int r, SegLazy val) {
		_upd(l, r, 1, 0, n, val);
	}

	void _upd(int l, int r, int ti, int tl, int tr, SegLazy val) {
		//cerr << tl << ' ' << tr << '\n';
		push(ti);
		if(l >= tr || r <= tl) return;
		if(l <= tl && r >= tr) {
			lazy[ti] = val;
			push(ti);
			return;
		}

		int tm = (tl+tr)/2;
		_upd(l, r, ti*2, tl, tm, val);
		_upd(l, r, ti*2+1, tm, tr, val);
		pull(ti);
	}
};

SegTree st(0);

void dfs1(int u) {
	if(u >= n) {
		tot[u] = 1;
		return;
	}
	tot[u] = tree[u].size();
	for(int v : tree[u]) {
		dfs1(v);
		tot[u] *= tot[v];
		tot[u] %= MOD;
	}
}

void dfs2(int u, int top) {
	if(u >= n) {
		contr[u-n] = top;
		return;
	}
	vec<int> pref_mul(tree[u].size()+1);
	vec<int> suf_mul(tree[u].size()+1);

	pref_mul[0] = 1;
	suf_mul[0] =1;

	for(int i = 0; i<tree[u].size(); i++) {
		pref_mul[i+1] = pref_mul[i]*tot[tree[u][i]];
		pref_mul[i+1] %= MOD;
		suf_mul[i+1] = suf_mul[i]*tot[tree[u][tree[u].size()-i-1]];
		suf_mul[i+1] %= MOD;
	}

	for(int i = 0; i<tree[u].size(); i++) {
		dfs2(tree[u][i], (top*pref_mul[i]*suf_mul[tree[u].size()-i-1]) % MOD);
	}
}


void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
	n = N;
	m = M;
	a = A;

	for(int i = 1; i<N+M; i++) {
		tree[P[i]].push_back(i);
	}

	dfs1(0);
	dfs2(0, 1);

	st = SegTree(m);
	for(int i = 0; i<m; i++) {
		//cerr << contr[i] << ' ';
		SegNode node = {{0, contr[i]}};
		st.set(i, node);
		st.upd(i, i+1, {A[i]});
	}
	//cerr << '\n';
	//cerr << st.data[1].sums[0] << '\n';
}

int32_t count_ways(int32_t L, int32_t R) {
	//cerr << "QUERY: " << L << ' ' << R << '\n';
	st.upd(L-n, R+1-n, {true});
	return st.data[1].sums[0] % MOD;
}

Compilation message

circuit.cpp: In member function 'SegLazy SegLazy::merge(SegLazy)':
circuit.cpp:24:16: warning: narrowing conversion of '(((int)((SegLazy*)this)->SegLazy::flip) ^ ((int)other.SegLazy::flip))' from 'int' to 'bool' [-Wnarrowing]
   24 |   return {flip ^ other.flip};
      |           ~~~~~^~~~~~~~~~~~
circuit.cpp: In function 'void dfs2(long long int, long long int)':
circuit.cpp:130:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |  for(int i = 0; i<tree[u].size(); i++) {
      |                 ~^~~~~~~~~~~~~~~
circuit.cpp:137:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |  for(int i = 0; i<tree[u].size(); i++) {
      |                 ~^~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int32_t, int32_t, std::vector<int>, std::vector<int>)':
circuit.cpp:160:24: warning: narrowing conversion of 'A.std::vector<int>::operator[](((std::vector<int>::size_type)i))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'bool' [-Wnarrowing]
  160 |   st.upd(i, i+1, {A[i]});
      |                        ^

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 1 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 1 ms 7256 KB Output is correct
5 Correct 1 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7512 KB Output is correct
11 Correct 3 ms 7512 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7376 KB Output is correct
4 Correct 1 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 1 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 1 ms 7256 KB Output is correct
9 Correct 1 ms 7256 KB Output is correct
10 Correct 1 ms 7256 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 1 ms 7256 KB Output is correct
13 Correct 1 ms 7256 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7256 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7512 KB Output is correct
19 Correct 3 ms 7512 KB Output is correct
20 Correct 2 ms 7256 KB Output is correct
21 Incorrect 2 ms 7256 KB 1st lines differ - on the 1st token, expected: '759476520', found: '705674784'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 10328 KB Output is correct
2 Correct 698 ms 13296 KB Output is correct
3 Correct 641 ms 13400 KB Output is correct
4 Correct 672 ms 13460 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 10328 KB Output is correct
2 Correct 698 ms 13296 KB Output is correct
3 Correct 641 ms 13400 KB Output is correct
4 Correct 672 ms 13460 KB Output is correct
5 Correct 549 ms 10328 KB Output is correct
6 Correct 716 ms 13500 KB Output is correct
7 Correct 729 ms 13400 KB Output is correct
8 Correct 690 ms 13400 KB Output is correct
9 Correct 303 ms 7256 KB Output is correct
10 Correct 681 ms 7512 KB Output is correct
11 Correct 670 ms 7512 KB Output is correct
12 Correct 617 ms 7764 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 1 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 1 ms 7256 KB Output is correct
5 Correct 1 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 2 ms 7256 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7512 KB Output is correct
11 Correct 3 ms 7512 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 470 ms 10328 KB Output is correct
14 Correct 698 ms 13296 KB Output is correct
15 Correct 641 ms 13400 KB Output is correct
16 Correct 672 ms 13460 KB Output is correct
17 Correct 549 ms 10328 KB Output is correct
18 Correct 716 ms 13500 KB Output is correct
19 Correct 729 ms 13400 KB Output is correct
20 Correct 690 ms 13400 KB Output is correct
21 Correct 303 ms 7256 KB Output is correct
22 Correct 681 ms 7512 KB Output is correct
23 Correct 670 ms 7512 KB Output is correct
24 Correct 617 ms 7764 KB Output is correct
25 Correct 740 ms 17484 KB Output is correct
26 Correct 683 ms 17488 KB Output is correct
27 Correct 618 ms 17488 KB Output is correct
28 Correct 638 ms 17492 KB Output is correct
29 Correct 739 ms 32080 KB Output is correct
30 Correct 692 ms 32080 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7376 KB Output is correct
4 Correct 1 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 1 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 1 ms 7256 KB Output is correct
9 Correct 1 ms 7256 KB Output is correct
10 Correct 1 ms 7256 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 1 ms 7256 KB Output is correct
13 Correct 1 ms 7256 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7256 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7512 KB Output is correct
19 Correct 3 ms 7512 KB Output is correct
20 Correct 2 ms 7256 KB Output is correct
21 Incorrect 2 ms 7256 KB 1st lines differ - on the 1st token, expected: '759476520', found: '705674784'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7376 KB Output is correct
4 Correct 1 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 1 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 1 ms 7256 KB Output is correct
9 Correct 1 ms 7256 KB Output is correct
10 Correct 1 ms 7256 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 1 ms 7256 KB Output is correct
13 Correct 1 ms 7256 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7256 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7512 KB Output is correct
19 Correct 3 ms 7512 KB Output is correct
20 Correct 2 ms 7256 KB Output is correct
21 Incorrect 2 ms 7256 KB 1st lines differ - on the 1st token, expected: '759476520', found: '705674784'
22 Halted 0 ms 0 KB -