Submission #635187

#	Time	Username	Problem	Language	Result	Execution time	Memory
635187		youngyojun	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1352 ms	34868 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MOD = 1'000'002'022;
const int MAXN = 100'055;

inline void add(int &a, int b) { a += b; if(MOD <= a) a -= MOD; }
inline void sub(int &a, int b) { a -= b; if(a < 0) a += MOD; }

struct SEG {
	int d[MAXN*4][2];
	bitset<MAXN*4> df;
	
	vector<int> *Q;
	int *A;
	
	void init(int i, int s, int e) {
		if(s == e) {
			d[i][(*Q)[s]] = A[s];
			return;
		}
		
		int m = s+e >> 1;
		init(i<<1, s, m);
		init(i<<1|1, m+1, e);
		
		for(int j = 2; j--;) {
			d[i][j] = d[i<<1][j];
			add(d[i][j], d[i<<1|1][j]);
		}
	}
	
	pii f(int i, int s, int e, int p, int q) {
		if(q < s || e < p) return {0, 0};
		if(p <= s && e <= q) {
			swap(d[i][0], d[i][1]);
			df[i] = !df[i];
			return {d[i][1], d[i][0]};
		}
		int m = s+e >> 1;
		pii r = f(i<<1, s, m, p, q);
		pii t = f(i<<1|1, m+1, e, p, q);
		add(r.fi, t.fi); add(r.se, t.se);
		for(int j = 2; j--;) {
			d[i][j] = d[i<<1][j];
			add(d[i][j], d[i<<1|1][j]);
		}
		if(df[i]) {
			swap(d[i][0], d[i][1]);
			swap(r.fi, r.se);
		}
		return r;
	}
} seg;

vector<int> G[MAXN*2];

int A[MAXN*2], B[MAXN*2];

int N, M, Ans;

void dfs1(int i) {
	int r = max(1, sz(G[i]));
	for(int v : G[i]) {
		dfs1(v);
		r = ll(r) * B[v] % MOD;
	}
	B[i] = r;
}

void dfs2(int i) {
	int u = A[i];
	int dg = sz(G[i]);
	vector<int> L(dg, 1), R(dg, 1);
	for(int j = 1; j < dg; j++)
		L[j] = ll(L[j-1]) * B[G[i][j-1]] % MOD;
	for(int j = dg-2; 0 <= j; j--)
		R[j] = ll(R[j+1]) * B[G[i][j+1]] % MOD;
	for(int j = dg; j--;) {
		int v = G[i][j];
		A[v] = ll(u) * L[j] % MOD * R[j] % MOD;
		dfs2(v);
	}
}

void init(int N, int M, std::vector<int> P, std::vector<int> Q) {
	::N = N; ::M = M;
	for(int i = N+M; --i;) G[P[i]].eb(i);
	dfs1(0); A[0] = 1; dfs2(0);
	for(int i = 0; i < M; i++) A[i] = A[N+i];
	seg.A = A; seg.Q = &Q;
	seg.init(1, 0, M-1);
	B[0] = 0;
	for(int i = 1; i <= M; i++) {
		B[i] = B[i-1];
		add(B[i], A[i-1]);
	}
	for(int i = M; i--;) if(Q[i]) add(Ans, A[i]);
}

int count_ways(int L, int R) {
	L -= N; R -= N;
	int r = seg.f(1, 0, M-1, L, R).se;
	add(Ans, B[R+1]); sub(Ans, B[L]);
	add(r, r); sub(Ans, r);
	return Ans;
}

Compilation message (stderr)

circuit.cpp: In member function 'void SEG::init(int, int, int)':
circuit.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int m = s+e >> 1;
      |           ~^~
circuit.cpp: In member function 'pii SEG::f(int, int, int, int, int)':
circuit.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int m = s+e >> 1;
      |           ~^~

• 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