Submission #1058730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058730		nvujica	Digital Circuit (IOI22_circuit)	C++17	50 / 100	3095 ms	24164 KiB

circuit

#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 (stderr)

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
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11