Submission #735862

#	Time	Username	Problem	Language	Result	Execution time	Memory
735862		AdamGS	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1314 ms	40480 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1000000000+2022;
const int LIM=2e5+7;
vector<int>V[LIM];
ll ilo[LIM], tr[4*LIM], sum[4*LIM], lazy[4*LIM], N=1;
void DFS(int x) {
	ilo[x]=max(1, (int)V[x].size());
	for(auto i : V[x]) {
		DFS(i);
		ilo[x]=(ilo[x]*ilo[i])%MOD;
	}
}
void DFS2(int x, ll akt) {
	if(!V[x].size()) {
		sum[N+x]=akt;
		return;
	}
	vector<ll>pref(V[x].size()), suf(V[x].size());
	rep(i, V[x].size()) {
		pref[i]=ilo[V[x][i]];
		suf[V[x].size()-i-1]=ilo[V[x][V[x].size()-i-1]];
		if(i) {
			pref[i]=(pref[i]*pref[i-1])%MOD;
			suf[V[x].size()-i-1]=(suf[V[x].size()-i-1]*suf[V[x].size()-i])%MOD;
		}
	}
	rep(i, V[x].size()) {
		ll p=akt;
		if(i) p=(p*pref[i-1])%MOD;
		if(i+1<V[x].size()) p=(p*suf[i+1])%MOD;
		DFS2(V[x][i], p);
	}
}
void init(int n, int m, vector<int> P, vector<int> A) {
	while(N<n+m) N*=2;
	for(int i=1; i<P.size(); ++i) V[P[i]].pb(i);
	DFS(0);
	DFS2(0, 1);
	rep(i, m) if(A[i]) tr[N+n+i]=sum[N+n+i];
	for(int i=N-1; i; --i) {
		tr[i]=(tr[2*i]+tr[2*i+1])%MOD;
		sum[i]=(sum[2*i]+sum[2*i+1])%MOD;
	}
}
void spl(int v) {
	tr[2*v]=(sum[2*v]-tr[2*v]+MOD)%MOD;
	tr[2*v+1]=(sum[2*v+1]-tr[2*v+1]+MOD)%MOD;
	lazy[2*v]^=1;
	lazy[2*v+1]^=1;
	lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b) {
	if(r<a || l>b) return;
	if(a<=l && r<=b) {
		tr[v]=(sum[v]-tr[v]+MOD)%MOD;
		lazy[v]^=1;
		return;
	}
	if(lazy[v]) spl(v);
	int mid=(l+r)/2;
	upd(2*v, l, mid, a, b);
	upd(2*v+1, mid+1, r, a, b);
	tr[v]=(tr[2*v]+tr[2*v+1])%MOD;
}
int count_ways(int l, int r) {
  upd(1, 0, N-1, l, r);
	return tr[1];
}

Compilation message (stderr)

circuit.cpp: In function 'void DFS2(int, ll)':
circuit.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
circuit.cpp:28:2: note: in expansion of macro 'rep'
   28 |  rep(i, V[x].size()) {
      |  ^~~
circuit.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
circuit.cpp:36:2: note: in expansion of macro 'rep'
   36 |  rep(i, V[x].size()) {
      |  ^~~
circuit.cpp:39:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   if(i+1<V[x].size()) p=(p*suf[i+1])%MOD;
      |      ~~~^~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i=1; i<P.size(); ++i) V[P[i]].pb(i);
      |               ~^~~~~~~~~

• 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