Submission #629975

#	Time	Username	Problem	Language	Result	Execution time	Memory
629975		handlename	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1392 ms	41876 KiB

circuit

#include <bits/stdc++.h>
//#include "circuit.h"
using namespace std;
#define pb push_back
#define mp make_pair
const int MOD=1e9+2022;
int n,mm,par[200001],arr[200001];
vector<int> adj[200001];
long long mult[200001],ans[200001];
long long dfs(int x){
	mult[x]=max((int)adj[x].size(),1);
	for (auto i:adj[x]){
		mult[x]*=dfs(i);
		mult[x]%=MOD;
	}
	return mult[x];
}
void dfs(int x,long long d){
	ans[x]=d;
	long long pre[adj[x].size()],suf[adj[x].size()];
	pre[0]=suf[adj[x].size()-1]=1;
	for (int i=1;i<(int)adj[x].size();i++){
		pre[i]=pre[i-1]*mult[adj[x][i-1]];
		pre[i]%=MOD;
	}
	for (int i=adj[x].size()-2;i>=0;i--){
		suf[i]=suf[i+1]*mult[adj[x][i+1]];
		suf[i]%=MOD;
	}
	for (int i=0;i<(int)adj[x].size();i++){
		long long cur=d;
		cur*=pre[i];
		cur%=MOD;
		cur*=suf[i];
		cur%=MOD;
		dfs(adj[x][i],cur);
	}
}
struct node{
	node *l,*r;
	int s,m,e;
	long long val,sum;
	bool flip;
	node(int ss,int ee){
		s=ss;
		e=ee;
		m=(s+e)/2;
		flip=false;
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			val=l->val+r->val;
			sum=l->sum+r->sum;
			val%=MOD;
			sum%=MOD;
		}
		else {
			sum=ans[s];
			val=ans[s]*arr[s];
		}
	}
	long long value(){
		if (s==e){
			if (flip) val=sum-val;
			flip=false;
			return val;
		}
		if (flip){
			val=sum-val;
			l->flip=!(l->flip);
			r->flip=!(r->flip);
		}
		flip=false;
		return val;
	}
	void upd(int x,int y){
		value();
		if (s==x && e==y){
			flip=!flip;
			return;
		}
		if (x>m) r->upd(x,y);
		else if (y<=m) l->upd(x,y);
		else l->upd(x,m),r->upd(m+1,y);
		val=l->value()+r->value();
		val%=MOD;
	}
}*root;
void init(int N,int M,vector<int> P,vector<int> A){
	n=N;
	mm=M;
	for (int i=1;i<n+mm;i++){
		par[i]=P[i];
		adj[par[i]].pb(i);
	}
	for (int i=0;i<mm;i++){
		arr[n+i]=A[i];
	}
	dfs(0);
	dfs(0,1);
	root=new node(n,n+mm-1);
}
int count_ways(int l,int r){
	root->upd(l,r);
	return ((root->value())%MOD+MOD)%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