Submission #710664

#	Time	Username	Problem	Language	Result	Execution time	Memory
710664		myrcella	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1137 ms	36536 KiB

circuit

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000002022
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "circuit.h"

const int maxn = 200010;
int a[maxn];
vector <int> edge[maxn];
int NN,MM;
pii tree[maxn*4];
int add[maxn*4];
int prod[maxn],cont[maxn];

void initt(int c,int cl,int cr) {
	if (cl==cr) {
		tree[c] = {a[cl]*cont[cl],(a[cl]^1)*cont[cl]};
		return;
	}
	int mid=cl+cr>>1;
	initt(c<<1,cl,mid);
	initt(c<<1|1,mid+1,cr);
	tree[c].fi = (tree[c<<1].fi + tree[c<<1|1].fi)%mod;
	tree[c].se = (tree[c<<1].se + tree[c<<1|1].se)%mod;
//	cout<<cl<<" "<<cr<<" "<<tree[c].fi<<" "<<tree[c].se<<endl;
}

void update(int c,int cl,int cr,int l,int r) {
	if (l<=cl and cr<=r) {
		add[c]^=1;
		swap(tree[c].fi,tree[c].se);
		return;
	}
	if (add[c]==1) {
		add[c<<1]^=1,add[c<<1|1]^=1;
		swap(tree[c<<1].fi,tree[c<<1].se);
		swap(tree[c<<1|1].fi,tree[c<<1|1].se);
		add[c] = 0;
	}
	int mid=cl+cr>>1;
	if (l<=mid) update(c<<1,cl,mid,l,r);
	if (r>mid) update(c<<1|1,mid+1,cr,l,r);
	tree[c].fi = (tree[c<<1].fi + tree[c<<1|1].fi)%mod;
	tree[c].se = (tree[c<<1].se + tree[c<<1|1].se)%mod;
	return;
}

void dfs1(int u) {
	prod[u] = SZ(edge[u]);
	if (prod[u]==0) prod[u]=1;
	for (int v:edge[u]) {
		dfs1(v);
		prod[u] = 1ll*prod[u]*prod[v]%mod;
	}
	return;
}

void dfs2(int u,int cur) {
	if (SZ(edge[u])==0) {
		cont[u]=cur;
		return;
	}
	vector <int> pre,suf;
	for (int v:edge[u]) {
		pre.pb(prod[v]);
		suf.pb(prod[v]);
	}
	rep(i,1,SZ(pre)) pre[i] = 1ll*pre[i-1]*pre[i]%mod;
	for (int i = SZ(suf)-2;i>=0;i--) suf[i] = 1ll*suf[i+1]*suf[i]%mod;	
	rep(i,0,SZ(edge[u])) {
		int tmp = 1;
		if (i>0) tmp = 1ll*tmp*pre[i-1]%mod;
		if (i+1<SZ(edge[u])) tmp = 1ll*tmp*suf[i+1]%mod;
		dfs2(edge[u][i],1ll*cur*tmp%mod);
	}
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	NN=N,MM=M;
	rep(i,1,SZ(P)) {
		edge[P[i]].pb(i);
	}
	rep(i,0,SZ(A)) a[i+N]=A[i];
	dfs1(0);
	dfs2(0,1);
	initt(1,N,N+M-1);
}

int count_ways(int L, int R) {
	update(1,NN,NN+MM-1,L,R);
	return tree[1].fi;
}

Compilation message (stderr)

circuit.cpp: In function 'void initt(int, int, int)':
circuit.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int mid=cl+cr>>1;
      |          ~~^~~
circuit.cpp: In function 'void update(int, int, int, int, int)':
circuit.cpp:59:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |  int mid=cl+cr>>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