Submission #794354

#	Time	Username	Problem	Language	Result	Execution time	Memory
794354		IvanJ	Digital Circuit (IOI22_circuit)	C++17	100 / 100	953 ms	43464 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5;
const int MOD = 1000002022;

int mult(ll x, ll y) {return x * y % MOD;}
int add(int x, int y) {x += y;if(x >= MOD) x -= MOD;return x;}

int n, m;
int c[maxn];
int prod[maxn];
vector<int> adj[maxn];
vector<int> pref[maxn], suff[maxn];

struct Seg {
	int pot;
	vector<ii> T;
	vector<int> L;
	void init(int sz) {
		pot = 1;
		while(pot < sz) pot <<= 1;
		for(int i = 0;i < (pot << 1);i++) T.pb({0, 0}), L.pb(0);
		for(int i = 0;i < m;i++) 
			T[i + pot] = {0, c[i]};
		for(int i = pot - 1;i > 0;i--) {
			T[i].x = add(T[i * 2].x, T[i * 2 + 1].x);
			T[i].y = add(T[i * 2].y, T[i * 2 + 1].y);
		}
	}
	
	void prop(int x) {
		if(L[x] == 0) return;
		swap(T[x].x, T[x].y);
		if(x < pot)
			L[x * 2] ^= 1, L[x * 2 + 1] ^= 1;
		L[x] = 0;
	}
	
	void update(int x, int lo, int hi, int a, int b) {
		prop(x);
		if(hi < a || b < lo) return;
		if(a <= lo && hi <= b) {
			L[x] ^= 1;
			prop(x);
			return;
		}
		int mid = (lo + hi) / 2;
		update(x * 2, lo, mid, a, b);
		update(x * 2 + 1, mid + 1, hi, a, b);
		T[x].x = add(T[x * 2].x, T[x * 2 + 1].x);
		T[x].y = add(T[x * 2].y, T[x * 2 + 1].y);
	}
	
	void toggle(int lo, int hi) {update(1, 0, pot - 1, lo, hi);}
	
	int get() {return T[1].x;}
} S;

void dfs(int x) {
	prod[x] = (int)adj[x].size();
	for(int y : adj[x]) dfs(y);
	
	for(int y : adj[x]) {
		int p = 1;
		if(pref[x].size()) p = pref[x].back();
		pref[x].pb(mult(p, prod[y]));
	}
	reverse(all(adj[x]));
	for(int y : adj[x]) {
		int p = 1;
		if(suff[x].size()) p = suff[x].back();
		suff[x].pb(mult(p, prod[y]));
	}
	reverse(all(suff[x]));
	reverse(all(adj[x]));
	
	if(pref[x].size())
		prod[x] = mult(prod[x], pref[x].back());
	if(adj[x].size() == 0) 
		prod[x] = 1;
}

void solve(int x, int sol) {
	if(x >= n) c[x - n] = sol;
	int i = 0;
	for(int y : adj[x]) {
		int l = 1;
		if(i) l = pref[x][i - 1];
		int r = 1;
		if(i < (int)adj[x].size() - 1) r = suff[x][i + 1];
		solve(y, mult(sol, mult(l, r)));
		i++;
	}
}

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);
		
	dfs(0);
	solve(0, 1);
	S.init(m);
	for(int i = 0;i < m;i++) 
		if(A[i]) S.toggle(i, i);
}

int count_ways(int L, int R) {
	L -= n, R -= n;
	S.toggle(L, R);
	return S.get();
}

• 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