Submission #1172832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172832		thelegendary08	디지털 회로 (IOI22_circuit)	C++17	4 / 100	355 ms	34472 KiB

circuit

#include "circuit.h"
// #include<stub.cpp>
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define f0r(i,n) for(int i = 0;  i< n; i++)
#define mp make_pair
using namespace std;
vector<signed> par;
vector<signed> state;
vector<vi> adj;
int n,m;
const int mod = 1e9 + 2022;
const int mxn = 2e5 + 5;
vector<vi>dp(mxn, vi(2));
vi dep(mxn);
vi cont(mxn);
int binexp(int a, int b){
	int ret = 1;
	f0r(i, 30){
		if(b & (1 << i)){
			ret *= a;
			ret %= mod;
		}
		a *= a;
		a %= mod;
	}
	return ret;
}
vi lef(mxn, -1);
vi rig(mxn, -1);
vi tl(mxn);
vi tr(mxn);
vi sts(mxn);
vi tree(mxn);
vi totcont(mxn);
int dfs(int node, int from){
	int cur = 1;
	int curtl = 1e9;
	int curtr = -1;
	
	for(auto u : adj[node]){
		if(u != from){
			if(lef[node] == -1)lef[node] = u;
			else rig[node] = u;
			dep[u] = 1 + dep[node];
			cur += dfs(u, node);
			curtl = min(curtl, tl[u]);
			curtr = max(curtr, tr[u]);
			
		}
	}
	if(node >= n){
		cur = 0;
		tl[node] = node - n;
		tr[node] = node - n;
	}
	else{
		tl[node] = curtl;
		tr[node] = curtr;
	}
	sts[node] = cur;
	return sts[node];
}
int dfs2(int node, int from){
	int curcont = 0;
	for(auto u : adj[node]){
		if(u != from){
			curcont += dfs2(u, node);
			curcont %= mod;
			// cout<<tree[u]<<" tree u "<<'\n';
			totcont[node] += totcont[u];
			totcont[node] %= mod;
		}
	}
	if(sts[node] == 0){
		tree[node] += state[node - n] * cont[node - n];
		tree[node] %= mod;
		totcont[node] = cont[node - n];
	}
	else{
		tree[node] = curcont;
	}
	return tree[node];
}
vi la(mxn);
void pull(int v){
	tree[v] = tree[lef[v]] + tree[rig[v]];
	tree[v] %= mod;
}
void toggle(int v){
	la[v] = 1;
	tree[v] = totcont[v] - tree[v];
	tree[v] %= mod;
	if(tree[v] < 0)tree[v] += mod;
}
void push(int v){
	if(la[v]){
		toggle(lef[v]);
		toggle(rig[v]);
		la[v] = 0;
	}
	
}
void update(int v, int l, int r){
	// cout<<"UPDATE "<<v<<'\n';
	if(tl[v] > r || tr[v] < l){
		return;
	}
	if(tl[v] >= l && tr[v] <= r){
		// cout<<"INRANGW "<<v<<'\n';
		// cout<<tree[v]<<'\n';
		toggle(v);
		// cout<<tree[v]<<'\n';
	}
	else{
		push(v);
		update(lef[v], l, r);
		update(rig[v], l, r);
		pull(v);
	}
}
void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
	n = N; m = M; par = P; state = A;
	adj.resize(n + m);
	FOR(i, 1, n+m){
		adj[P[i]].pb(i);
	}
	dfs(0, -1);
	f0r(i, m){
		cont[i] = binexp(2, n - dep[i + n]);
	}
	
	dfs2(0, -1);
	f0r(i, n+m){
		// cout<<i<<' '<<tree[i]<<'\n';
	}
	// cout<< '\n';
	f0r(i,n+m){
		// cout<<tl[i]<<' '<<tr[i]<<'\n';
	}
	// cout<<'\n';
}

signed count_ways(signed l, signed r) {
	l -= n; r -= n;
	update(0, l, r);
	f0r(i, n+m){
		// cout<<tree[i]<<'\n';
	}
	// cout<< '\n';
	return tree[0];
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11