Submission #1235098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235098		AMnu	Digital Circuit (IOI22_circuit)	C++20	100 / 100	421 ms	33684 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 2e5+5, MOD = 1e9+2022;

int N, M;
ll S[MAXN], C[MAXN];
vector <int> adj[MAXN];

struct segment {
	int L, R;
	ll val, mx;
	bool flip;
	segment *lef, *rig;
	
	segment(int x,int y) {
		L = x; R = y;
		val = 0; flip = 0;
		if (L == R) {
			mx = C[L];
			return;
		}
		int mid = (L+R)/2;
		lef = new segment(L,mid);
		rig = new segment(mid+1,R);
		mx = lef->mx + rig->mx;
	}
	
	void update(int x,int y) {
		if (x > R || y < L) {
			return;
		}
		if (x <= L && y >= R) {
			val = mx - val;
			flip ^= 1;
			return;
		}
		if (flip) {
			flip = 0;
			lef->val = lef->mx - lef->val;
			rig->val = rig->mx - rig->val;
			lef->flip ^= 1;
			rig->flip ^= 1;
		}
		lef->update(x,y);
		rig->update(x,y);
		val = lef->val + rig->val;
	}
} tree(0,0);

void calc(int cur,ll val) {
	if (cur >= N) {
		C[cur] = val;
		return;
	}
	vector <ll> suf(adj[cur].size(),1);
	for (int i=adj[cur].size()-1;i>0;i--) {
		suf[i-1] = S[adj[cur][i]]*suf[i]%MOD;
	}
	ll pre = val;
	for (int i=0;i<(int)adj[cur].size();i++) {
		calc(adj[cur][i],pre*suf[i]%MOD);
		pre = pre*S[adj[cur][i]]%MOD;
	}
}

ll dfs(int cur) {
	if (cur >= N) return S[cur] = 1;
	S[cur] = adj[cur].size();
	for (int next : adj[cur]) {
		S[cur] = S[cur]*dfs(next)%MOD;
	}
	return S[cur];
}

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]].push_back(i);
	}
	dfs(0);
	calc(0,1);
	tree = segment(N,N+M-1);
	for (int i=0;i<M;i++) {
		if (A[i]) {
			tree.update(i+N,i+N);
		}
	}
}

int count_ways(int L,int R) {
	tree.update(L,R);
	return tree.val % MOD;
}

• 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