oj.uz

Submission #955522

# Submission time Handle Problem Language Result Execution time Memory
955522 2024-03-30T19:31:30 Z StefanSebez Digital Circuit (IOI22_circuit) C++17
6 / 100
 725 ms 22812 KB 
#include "circuit.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int N=1e5+500;
const ll mod=1000002022;
ll Puta(ll a,ll b){a%=mod,b%=mod;ll x=a*b;x%=mod;return x;}
ll Plus(ll a,ll b){a%=mod,b%=mod;ll x=a+b;x%=mod;return x;}
vector<int>E[2*N+500];
int a[N+500],n,m,P[2*N+500];
ll res[N+500],dp[2*N+500][2],F[2*N+500],F1[2*N+500];
bool stepen2;
void DFSsetup(int u){
	if(E[u].empty()) return;
	F[u]=E[u].size();
	for(auto i:E[u]){
		DFSsetup(i);
		F[u]=Puta(F[u],F[i]);
	}
	for(auto i:E[u]){
		F1[i]=1;
		for(auto j:E[u]){
			if(j!=i) F1[i]=Puta(F1[i],F[j]);
		}
	}
}
void DFS(int u){
	if(E[u].empty()) return;
	for(auto i:E[u]) DFS(i);
	dp[u][1]=0;
	for(auto i:E[u]) dp[u][1]=Plus(dp[u][1],Puta(dp[i][1],F1[i]));
	//printf("%i: %lld %lld\n",u,dp[u][1],F[u]);
	/*int mask=0;
	while(mask< (1<<(E[u].size()))){
		ll temp1=1,sum=0;
		for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
			temp1=Puta(temp1,dp[E[u][i]][temp%2]);sum+=temp%2;
		}
		if(mask!=0) dp[u][1]=Plus(dp[u][1],Puta(sum,temp1));
		dp[u][0]=Plus(dp[u][0],Puta(E[u].size()-sum,temp1));
		mask++;
	}*/
	//dp[u][0]=F[u]-dp[u][1];
}
void Update1(int v){
	dp[v][1]=1-dp[v][1];
	dp[v][0]=1-dp[v][0];
	int u=P[v];
	while(u!=-1){
		dp[u][1]=0;
		for(auto i:E[u]) dp[u][1]=Plus(dp[u][1],Puta(dp[i][1],F1[i]));
		/*dp[u][1]=dp[u][0]=0;
		int mask=0;
		while(mask< (1<<(E[u].size()))){
			ll temp1=1,sum=0;
			for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
				temp1=Puta(temp1,dp[E[u][i]][temp%2]);sum+=temp%2;
			}
			if(mask!=0) dp[u][1]=Plus(dp[u][1],Puta(sum,temp1));
			dp[u][0]=Plus(dp[u][0],Puta(E[u].size()-sum,temp1));
			mask++;
		}*/
		u=P[u];
	}
}
int nc,root,lc[2*N],rc[2*N],sum[2*N],lazy[2*N];
void update(int &c,int ss,int se,int qval){
	if(!c) c=++nc;
	if(qval==0) return;
	sum[c]=se-ss+1-sum[c];
	lazy[c]++;lazy[c]%=2;
}
void push(int &c,int ss,int se){
	int mid=(ss+se)/2;
	update(lc[c],ss,mid,lazy[c]);
	update(rc[c],mid+1,se,lazy[c]);
	lazy[c]=0;
}
void Update(int &c,int ss,int se,int qs,int qe){
	if(!c) c=++nc;
	if(qs<=ss && se<=qe){
		update(c,ss,se,1);
		//printf("%i %i %i: %i\n",c,ss,se,sum[c]);
		return;
	}
	if(qe<ss || se<qs) return;
	int mid=(ss+se)/2;
	push(c,ss,se);
	Update(lc[c],ss,mid,qs,qe);Update(rc[c],mid+1,se,qs,qe);
	sum[c]=sum[lc[c]]+sum[rc[c]];
	//printf("%i %i %i: %i\n",c,ss,se,sum[c]);
}
int Get(int c,int ss,int se,int qs,int qe){
	//printf("%i %i %i: %i\n",c,ss,se,sum[c]);
	if(qs<=ss && se<=qe) return sum[c];
	if(qe<ss || se<qs) return 0;
	int mid=(ss+se)/2;
	push(c,ss,se);
	return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe);
}

int tajm,in[2*N],out[2*N],LL[2*N],RR[2*N];
void DFSsetup2(int u){
	in[u]=++tajm;
	for(auto i:E[u]) DFSsetup2(i);
	out[u]=tajm;
}
int lazy2[2*N];
void update2(int u,int qval){
	if(qval==0) return;
	dp[u][1]=F[u]-dp[u][1];
	lazy2[u]++;lazy2[u]%=2;
}
void push2(int u){
	for(auto i:E[u]) update2(i,lazy2[u]);
	lazy2[u]=0;
}
void Update2(int u,int qs,int qe){
	if(qs<=LL[u] && RR[u]<=qe) {update2(u,1);return;}
	if(qe<LL[u] || RR[u]<qs) return;
	push2(u);
	for(auto i:E[u]) Update2(i,qs,qe);
	dp[u][1]=0;
	for(auto i:E[u]) dp[u][1]=Plus(dp[u][1],Puta(dp[i][1],F1[i]));
	//printf("%i %i %i: %i\n",u,LL[u],RR[u],dp[u][1]);
}

void init(int N1, int M1, std::vector<int> P1, std::vector<int> A) {
	n=N1,m=M1;
	for(int i=0;i<P1.size();i++) P[i]=P1[i];
	for(int i=0;i<P1.size();i++){
		E[P[i]].pb(i);
	}
	for(int i=0;i<m;i++){
		dp[n+i][1]=A[i],dp[n+i][0]=1-A[i];
		a[i]=A[i];
		F[n+i]=1;
	}
	DFSsetup2(0);
	for(int i=0;i<n+m;i++){
		int lb=lower_bound(in+n,in+n+m-1,in[i])-in,ub=lower_bound(out+n,out+n+m-1,out[i])-out;
		LL[i]=lb,RR[i]=ub;
		//printf("%i: %i %i %i %i\n",i,in[i],out[i],LL[i],RR[i]);
	}
	DFSsetup(0);
	DFS(0);
	int temp=m,ct=0;while(temp>0) ct+=temp%2,temp/=2;if(ct==1) stepen2=true;
	if(!stepen2 || n<=5000) return;
	for(int i=n;i<n+m;i++) dp[i][1]=0;
	DFS(0);
	res[0]=dp[0][1];
	for(int i=0;i<m;i++){
		Update1(n+i);
		res[i+1]=dp[0][1];
	}
	for(int i=0;i<m;i++) if(a[i]==1) Update(root,0,m-1,i,i);
}

int count_ways(int L, int R) {
	if(n<=5000){
		Update2(0,L,R);
		return dp[0][1];
	}
	if(stepen2){
		Update(root,0,m-1,L-n,R-n);
		return res[Get(root,0,m-1,0,m-1)];
	}
	for(int i=L;i<=R;i++) Update1(i);
	return dp[0][1];
}

Compilation message

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:134:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |  for(int i=0;i<P1.size();i++) P[i]=P1[i];
      |              ~^~~~~~~~~~
circuit.cpp:135:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |  for(int i=0;i<P1.size();i++){
      |              ~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14168 KB Output is correct
2 Correct 3 ms 14168 KB Output is correct
3 Correct 10 ms 14168 KB Output is correct
4 Correct 10 ms 14168 KB Output is correct
5 Correct 11 ms 14168 KB Output is correct
6 Correct 11 ms 14168 KB Output is correct
7 Correct 10 ms 14340 KB Output is correct
8 Correct 10 ms 14168 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14168 KB Output is correct
2 Correct 3 ms 14168 KB Output is correct
3 Correct 4 ms 14168 KB Output is correct
4 Incorrect 3 ms 14168 KB 3rd lines differ - on the 1st token, expected: '810019272', found: '-189982750'
5 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14168 KB Output is correct
2 Correct 3 ms 14168 KB Output is correct
3 Correct 10 ms 14168 KB Output is correct
4 Correct 10 ms 14168 KB Output is correct
5 Correct 11 ms 14168 KB Output is correct
6 Correct 11 ms 14168 KB Output is correct
7 Correct 10 ms 14340 KB Output is correct
8 Correct 10 ms 14168 KB Output is correct
9 Correct 3 ms 14168 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 4 ms 14168 KB Output is correct
12 Incorrect 3 ms 14168 KB 3rd lines differ - on the 1st token, expected: '810019272', found: '-189982750'
13 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 19484 KB Output is correct
2 Correct 697 ms 22696 KB Output is correct
3 Correct 711 ms 22344 KB Output is correct
4 Correct 647 ms 22812 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 19484 KB Output is correct
2 Correct 697 ms 22696 KB Output is correct
3 Correct 711 ms 22344 KB Output is correct
4 Correct 647 ms 22812 KB Output is correct
5 Correct 519 ms 19300 KB Output is correct
6 Correct 725 ms 22468 KB Output is correct
7 Correct 686 ms 22308 KB Output is correct
8 Correct 623 ms 22188 KB Output is correct
9 Incorrect 320 ms 14168 KB 8th lines differ - on the 1st token, expected: '500917550', found: '-499084472'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14168 KB Output is correct
2 Correct 3 ms 14168 KB Output is correct
3 Correct 4 ms 14168 KB Output is correct
4 Incorrect 3 ms 14168 KB 3rd lines differ - on the 1st token, expected: '810019272', found: '-189982750'
5 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14168 KB Output is correct
2 Correct 3 ms 14168 KB Output is correct
3 Correct 10 ms 14168 KB Output is correct
4 Correct 10 ms 14168 KB Output is correct
5 Correct 11 ms 14168 KB Output is correct
6 Correct 11 ms 14168 KB Output is correct
7 Correct 10 ms 14340 KB Output is correct
8 Correct 10 ms 14168 KB Output is correct
9 Correct 3 ms 14168 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 4 ms 14168 KB Output is correct
12 Incorrect 3 ms 14168 KB 3rd lines differ - on the 1st token, expected: '810019272', found: '-189982750'
13 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14168 KB Output is correct
2 Correct 3 ms 14168 KB Output is correct
3 Correct 10 ms 14168 KB Output is correct
4 Correct 10 ms 14168 KB Output is correct
5 Correct 11 ms 14168 KB Output is correct
6 Correct 11 ms 14168 KB Output is correct
7 Correct 10 ms 14340 KB Output is correct
8 Correct 10 ms 14168 KB Output is correct
9 Correct 3 ms 14168 KB Output is correct
10 Correct 3 ms 14168 KB Output is correct
11 Correct 4 ms 14168 KB Output is correct
12 Incorrect 3 ms 14168 KB 3rd lines differ - on the 1st token, expected: '810019272', found: '-189982750'
13 Halted 0 ms 0 KB -