Submission #629964

#	Time	Username	Problem	Language	Result	Execution time	Memory
629964		handlename	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3044 ms	8228 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,m,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);
	}
}
void init(int N,int M,vector<int> P,vector<int> A){
	n=N;
	m=M;
	for (int i=1;i<n+m;i++){
		par[i]=P[i];
		adj[par[i]].pb(i);
	}
	for (int i=0;i<m;i++){
		arr[n+i]=A[i];
	}
	dfs(0);
	dfs(0,1);
}
int count_ways(int l,int r){
	long long res=0;
	for (int i=l;i<=r;i++){
		arr[i]=1-arr[i];
	}
	for (int i=n;i<n+m;i++){
		res+=ans[i]*arr[i];
		res%=MOD;
	}
	return res;
}

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