Submission #1135027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135027		Saul0906	Digital Circuit (IOI22_circuit)	C++20	18 / 100	3012 ms	6812 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

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

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

void init(int n, int m, std::vector<int> p, std::vector<int> a) {
	rep(i,0,n+m) adj[p[i]].pb(i);
	rep(i,0,m) v[i+n]=a[i];
}

pll solve(int u){
	if(!adj[u].size()) return {v[u],v[u]^1};
	ll dp[adj[u].size()+1]{}, tot=0, ans=0;
	dp[0]=1;
	repa(e,adj[u]){
		pll x=solve(e);
		repr(i,adj[u].size()+1,0){
			dp[i]=(dp[i]*x.se);
			if(i) dp[i]+=(dp[i-1]*x.fi);
			dp[i]%=mod;
		}
	}
	rep(i,1,adj[u].size()+1){
		ans+=(dp[i]*i)%mod;
		ans%=mod;
		tot+=((adj[u].size()-i)*dp[i])%mod;
		tot%=mod;
	}
	tot+=(dp[0]*adj[u].size())%mod;
	tot%=mod;
	return {ans,tot};
}

int count_ways(int l, int r) {
	rep(i,l,r+1) v[i]^=1;
	return solve(0).fi;
}

• 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