Submission #1059935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059935		nvujica	Digital Circuit (IOI22_circuit)	C++17	100 / 100	762 ms	34752 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 umn[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;
	
	umn[x] = 1;
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
//		d[x2] = d[x] + 1;
		dfs1(x2);
		umn[x] = mul(umn[x], umn[x2]);
	}
	
	if(x < n) umn[x] = mul(umn[x], v[x].size());
}

void dfs2(int x){
	int c = v[x].size();
	
	vector<int> pref(c + 2);
	vector<int> suff(c + 2);
	
	pref[0] = 1;
	
	for(int i = 0; i < c; i++){
		int x2 = v[x][i];
		
		pref[i + 1] = mul(pref[i], umn[x2]);
	}
	
	suff[c + 1] = 1;
	
	for(int i = c - 1; i >= 0; i--){
		int x2 = v[x][i];
		
		suff[i + 1] = mul(suff[i + 2], umn[x2]);
	}
	
	for(int i = 0; i < c; i++){
		int x2 = v[x][i];
		
		fakt[x2] = mul(fakt[x], mul(pref[i], suff[i + 2]));
		dfs2(x2);
	}
}

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);
	
//	for(int i = 0; i < n + m; i++){
//		cout << umn[i] << ' ';
//	}
//	cout << endl;
//	
//	for(int i = 0; i < n + m; i++){
//		cout << fakt[i] << ' ';
//	}
//	cout << endl;
	
//	cout << "ovdje " << endl;
	
	for(int i = 0; i < m; i++){
		tour[off + i][A[i]] = fakt[n + i];
	}
	
	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]);
	}
}


int count_ways(int L, int R){
	update(1, 0, off, L - n, R - n + 1);
	
	return tour[1][1];
}

Compilation message (stderr)

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

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11