제출 #748843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748843		QwertyPi	디지털 회로 (IOI22_circuit)	C++17	100 / 100	1104 ms	28628 KiB

circuit

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

const int N_MAX = 2e5 + 11;
const int MOD = 1000002022;
vector<int> G[N_MAX];
int f[N_MAX], g[N_MAX];

void dfsU(int v){
	f[v] = G[v].empty() ? 1 : G[v].size();
	for(auto u : G[v]){
		dfsU(u);
		f[v] = (f[v] * f[u]) % MOD;
	}
}

int a[N_MAX << 2];
void upd(int pos, int val, int v, int l, int r){
	if(l == r) a[v] = val;
	else {
		int m = (l + r) / 2;
		if(pos <= m){
			upd(pos, val, v * 2 + 1, l, m);
		}else{
			upd(pos, val, v * 2 + 2, m + 1, r);
		}
		a[v] = a[v * 2 + 1] * a[v * 2 + 2] % MOD;
	}
}

int qry(int ql, int qr, int v, int l, int r){
	if(qr < l || r < ql) return 1;
	if(ql <= l && r <= qr) return a[v];
	int m = (l + r) / 2;
	
	int qx = qry(ql, qr, v * 2 + 1, l, m);
	int qy = qry(ql, qr, v * 2 + 2, m + 1, r);
	return qx * qy % MOD;
}

int qry_except(int x, int V){
	int qx = qry(0, x - 1, 0, 0, V - 1);
	int qy = qry(x + 1, V - 1, 0, 0, V - 1);
	return qx * qy % MOD;
}

void dfsD(int v){
	
	int V = G[v].size();
	for(int i = 0; i < V; i++){
		int u = G[v][i];
		upd(i, f[u], 0, 0, V - 1);
	}
	for(int i = 0; i < V; i++){
		int u = G[v][i];
		g[u] = g[v] * qry_except(i, V) % MOD;
	}
	for(int i = 0; i < V; i++){
		dfsD(G[v][i]);
	} 
}

int ac[N_MAX];
int N, M;

int norm(int x){
	return (x % MOD + MOD) % MOD;
}

namespace SegTree{
	int s[N_MAX << 2], t[N_MAX << 2], lz[N_MAX << 2];
	void push(int v){
		if(lz[v]){
			t[v * 2 + 1] = norm(s[v * 2 + 1] - t[v * 2 + 1]);
			t[v * 2 + 2] = norm(s[v * 2 + 2] - t[v * 2 + 2]);
			lz[v * 2 + 1] ^= 1;
			lz[v * 2 + 2] ^= 1;
			lz[v] = 0;
		}
	}
	void build(int v, int l, int r){
		if(l == r){
			s[v] = g[l];
			t[v] = g[l] * ac[l];
		}else{
			int m = (l + r) / 2;
			build(v * 2 + 1, l, m);
			build(v * 2 + 2, m + 1, r);
			s[v] = norm(s[v * 2 + 1] + s[v * 2 + 2]);
			t[v] = norm(t[v * 2 + 1] + t[v * 2 + 2]);
		}
	}
	void toggle(int ql, int qr, int v, int l, int r){
		if(qr < l || r < ql) return;
		if(ql <= l && r <= qr){
			t[v] = norm(s[v] - t[v]);
			lz[v] ^= 1;
			return;
		}
		push(v);
		int m = (l + r) / 2;
		toggle(ql, qr, v * 2 + 1, l, m);
		toggle(ql, qr, v * 2 + 2, m + 1, r);
		t[v] = norm(t[v * 2 + 1] + t[v * 2 + 2]);
	}
	int query(){
		return t[0];
	}
};
void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) {
	::N = N; ::M = M;
	for(int i = 1; i < N + M; i++){
		G[P[i]].push_back(i);
	}
	dfsU(0);
	g[0] = 1; dfsD(0);
	
	for(int i = N; i < N + M; i++){
		ac[i] = A[i - N];
	}
	
	SegTree::build(0, N, N + M - 1);
}

int32_t count_ways(int32_t L, int32_t R) {
	SegTree::toggle(L, R, 0, N, N + M - 1);
	return SegTree::query();
}

• 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