제출 #1136923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136923		Saul0906	디지털 회로 (IOI22_circuit)	C++20	100 / 100	401 ms	52016 KiB

circuit

#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
#define rep(a,b,c) for(ll a=b; a<c; a++)
#define repr(a,b,c) for(ll a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define mid ((l+r)>>1)

using namespace std;
using vi = vector<int>;

const ll N=2e5+5, mod=1e9+2022;
vi adj[N];
ll v[N], sum[N], h[N];

struct segtree{
	segtree *left, *right;
	ll l, r, s[2], c[2], dp[3], lazy=0;
	void calc(){
		rep(i,0,2) c[i]=left->c[i]+right->c[i];
		rep(i,0,2) s[i]=(left->s[i]+right->s[i])%mod;
		rep(i,0,3) dp[i]=(left->dp[i]*right->dp[i])%mod;
	}
	segtree(int x, int y): l(x), r(y){
		if(l==r){
			c[1]=v[l];
			c[0]=c[1]^1;
			s[0]=c[0]*sum[l];
			s[1]=c[1]*sum[l];
			dp[0]=c[0];
			dp[1]=c[1];
			dp[2]=0;
			return;
		}
		left = new segtree(l,mid);
		right= new segtree(mid+1,r);
		calc();
	}
	void prop(){
		if(!lazy) return;
		swap(c[0],c[1]);
		swap(s[0],s[1]);
		lazy=0;
		if(l==r){
			swap(dp[0],dp[1]);
			return;
		}
		left->lazy^=1;
		right->lazy^=1;
		swap(dp[0],dp[2]);
	}
	void update(int x, int y){
		prop();
		if(y<l || r<x) return;
		if(x<=l && r<=y){
			lazy=1;
			prop();
			return;
		}
		left->update(x,y);
		right->update(x,y);
		calc();
	}
} *st;

void dfs(int u){
	h[u]=max((int)adj[u].size(),1);
	repa(v,adj[u]) dfs(v), h[u]=(h[u]*h[v])%mod;
}

void dfs2(int u){
	ll p[adj[u].size()+1], s[adj[u].size()+1], x=1;
	rep(i,0,adj[u].size()) x=(x*h[adj[u][i]])%mod, p[i+1]=x;
	x=1;
	repr(i,adj[u].size(),0) x=(x*h[adj[u][i]])%mod, s[i]=x;
	p[0]=1;
	s[adj[u].size()]=1;
	rep(i,0,adj[u].size()){
		int v=adj[u][i];
		sum[v]=(sum[u]*p[i]%mod*s[i+1]%mod);
		dfs2(v);
	}
	sum[u]=(sum[u]*p[adj[u].size()])%mod;
}

void init(int n, int m, std::vector<int> p, std::vector<int> a) {
	rep(i,1,n+m) adj[p[i]].pb(i);
	rep(i,0,m) v[i+n]=a[i];
	dfs(0);
	sum[0]=1;
	dfs2(0);
	st = new segtree(n,n+m-1);
}

int count_ways(int l, int r) {
	st->update(l,r);
	return st->s[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