oj.uz

Submission #1058730

# Submission time Handle Problem Language Result Execution time Memory
1058730 2024-08-14T13:03:43 Z nvujica Digital Circuit (IOI22_circuit) C++17
50 / 100
 3000 ms 24164 KB 
#include <bits/stdc++.h>
#include "circuit.h"

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 2e5 + 10, off = (1 << 17), mod = 1e9 + 2022;

int n, m;
int tour[2 * off][2];
int prop[2 * off];
int d[maxn];
int pot[maxn];
vector <int> v[maxn];
//int stanje[maxn];
int fakt[maxn];
int siz[maxn];

int add(int x, int y){
	return (x + y) % mod;
}

int mul(int x, int y){
	return ((ll)x * y) % mod;
}

void push(int x){
	if(x >= off || !prop[x]) return;
	
	prop[x] = 0;
	swap(tour[x * 2][0], tour[x * 2][1]);
	swap(tour[x * 2 + 1][0], tour[x * 2 + 1][1]);
	prop[x * 2] ^= 1;
	prop[x * 2 + 1] ^= 1;
}

void update(int x, int lo, int hi, int l, int r){
	push(x);
	
	if(hi <= l || r <= lo) return;
	
	if(l <= lo && hi <= r){
		swap(tour[x][0], tour[x][1]);
		prop[x] = 1;
		return;
	}
	
	int mid = (lo + hi) / 2;
	update(x * 2, lo, mid, l, r);
	update(x * 2 + 1, mid, hi, l, r);
	tour[x][0] = add(tour[x * 2][0], tour[x * 2 + 1][0]);
	tour[x][1] = add(tour[x * 2][1], tour[x * 2 + 1][1]);
}

void dfs1(int x){
//	cout << x << endl;
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
//		d[x2] = d[x] + 1;
		dfs1(x2);
		siz[x] += siz[x2];
	}
	
	siz[x] += (x < n);
}

void dfs2(int x){
//	cout << x << endl;
	
	if(x >= n) return;
	
	int l = v[x][0];
	int r = v[x][1];
	
	fakt[l] = mul(fakt[x], pot[siz[r]]);
	fakt[r] = mul(fakt[x], pot[siz[l]]);
	dfs2(l);
	dfs2(r);
}

void init(int N, int M, vector<int> P, vector<int> A){
	n = N;
	m = M;
	
	pot[0] = 1;
	for(int i = 1; i < maxn; i++){
		pot[i] = mul(pot[i - 1], 2);
	}
	
	for(int i = 1; i < n + m; i++){
//		par[i] = P[i];
		v[P[i]].push_back(i);
	}
	
//	cout << "tu sam " << endl;
	
	fakt[0] = 1;
	dfs1(0);
	dfs2(0);
	
//	cout << "ovdje " << endl;
	
	for(int i = 0; i < m; i++){
		tour[off + i][A[i]] = fakt[n + i];
//		stanje[n + i] = A[i];
	}
	
//	for(int i = 0; i < n + m; i++){
//		cout << siz[i] << ' ';
//	}
//	cout << endl;
	
	for(int x = off - 1; x >= 1; x--){
		tour[x][0] = add(tour[x * 2][0], tour[x * 2 + 1][0]);
		tour[x][1] = add(tour[x * 2][1], tour[x * 2 + 1][1]);
	}
	
//	cout << "gotov " << endl;
}


int count_ways(int L, int R){
	update(1, 0, off, L - n, R - n + 1);
//	
//	for(int i = L; i <= R; i++){
//		stanje[i] ^= 1;
//	}
//	
//	int sum = 0;
//	
//	for(int i = n; i < n + m; i++){
//		if(stanje[i]) sum = add(sum, pot[d[i] - 1]);
//	}
//	
//	return sum;
	
	return tour[1][1];
}

Compilation message

circuit.cpp: In function 'void dfs1(int)':
circuit.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Execution timed out 3095 ms 8536 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Execution timed out 3095 ms 8536 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 12632 KB Output is correct
2 Correct 581 ms 14424 KB Output is correct
3 Correct 504 ms 14424 KB Output is correct
4 Correct 520 ms 14424 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 12632 KB Output is correct
2 Correct 581 ms 14424 KB Output is correct
3 Correct 504 ms 14424 KB Output is correct
4 Correct 520 ms 14424 KB Output is correct
5 Correct 492 ms 12632 KB Output is correct
6 Correct 628 ms 14424 KB Output is correct
7 Correct 585 ms 14424 KB Output is correct
8 Correct 597 ms 14424 KB Output is correct
9 Correct 313 ms 10584 KB Output is correct
10 Correct 564 ms 10840 KB Output is correct
11 Correct 528 ms 10840 KB Output is correct
12 Correct 553 ms 10840 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10584 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 357 ms 12632 KB Output is correct
14 Correct 581 ms 14424 KB Output is correct
15 Correct 504 ms 14424 KB Output is correct
16 Correct 520 ms 14424 KB Output is correct
17 Correct 492 ms 12632 KB Output is correct
18 Correct 628 ms 14424 KB Output is correct
19 Correct 585 ms 14424 KB Output is correct
20 Correct 597 ms 14424 KB Output is correct
21 Correct 313 ms 10584 KB Output is correct
22 Correct 564 ms 10840 KB Output is correct
23 Correct 528 ms 10840 KB Output is correct
24 Correct 553 ms 10840 KB Output is correct
25 Correct 597 ms 16208 KB Output is correct
26 Correct 626 ms 16464 KB Output is correct
27 Correct 604 ms 16464 KB Output is correct
28 Correct 542 ms 16480 KB Output is correct
29 Correct 575 ms 24164 KB Output is correct
30 Correct 564 ms 24160 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Execution timed out 3095 ms 8536 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Execution timed out 3095 ms 8536 KB Time limit exceeded
3 Halted 0 ms 0 KB -