oj.uz

Submission #955526

# Submission time Handle Problem Language Result Execution time Memory
955526 2024-03-30T19:45:55 Z StefanSebez Digital Circuit (IOI22_circuit) C++17
18 / 100
 901 ms 20896 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;while(x<0) 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]=Plus(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]);
}
bool subtask6=true;
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);
	for(int i=0;i<n;i++) if(E[i].size()!=2) subtask6=false;
	int temp=m,ct=0;while(temp>0) ct+=temp%2,temp/=2;if(ct==1) stepen2=true;
	if(!stepen2 || subtask6) 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(subtask6){
		//for(int i=L;i<=R;i++) dp[i][1]=1-dp[i][1];
		//DFS(0);
		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 3 ms 14168 KB Output is correct
2 Correct 3 ms 14168 KB Output is correct
3 Correct 17 ms 14168 KB Output is correct
4 Correct 18 ms 14168 KB Output is correct
5 Correct 16 ms 14168 KB Output is correct
6 Correct 17 ms 14168 KB Output is correct
7 Correct 38 ms 14240 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 3 ms 14168 KB Output is correct
4 Correct 3 ms 14168 KB Output is correct
5 Correct 4 ms 14168 KB Output is correct
6 Incorrect 3 ms 14168 KB 1st lines differ - on the 1st token, expected: '706880838', found: '106303284'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.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 17 ms 14168 KB Output is correct
4 Correct 18 ms 14168 KB Output is correct
5 Correct 16 ms 14168 KB Output is correct
6 Correct 17 ms 14168 KB Output is correct
7 Correct 38 ms 14240 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 3 ms 14168 KB Output is correct
12 Correct 3 ms 14168 KB Output is correct
13 Correct 4 ms 14168 KB Output is correct
14 Incorrect 3 ms 14168 KB 1st lines differ - on the 1st token, expected: '706880838', found: '106303284'
15 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 18424 KB Output is correct
2 Correct 782 ms 20832 KB Output is correct
3 Correct 774 ms 20880 KB Output is correct
4 Correct 765 ms 20896 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 18424 KB Output is correct
2 Correct 782 ms 20832 KB Output is correct
3 Correct 774 ms 20880 KB Output is correct
4 Correct 765 ms 20896 KB Output is correct
5 Correct 618 ms 18420 KB Output is correct
6 Correct 901 ms 20832 KB Output is correct
7 Correct 845 ms 20876 KB Output is correct
8 Correct 696 ms 20888 KB Output is correct
9 Correct 334 ms 14168 KB Output is correct
10 Correct 648 ms 14424 KB Output is correct
11 Correct 642 ms 14408 KB Output is correct
12 Correct 649 ms 14424 KB Output is correct

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 3 ms 14168 KB Output is correct
4 Correct 3 ms 14168 KB Output is correct
5 Correct 4 ms 14168 KB Output is correct
6 Incorrect 3 ms 14168 KB 1st lines differ - on the 1st token, expected: '706880838', found: '106303284'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.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 17 ms 14168 KB Output is correct
4 Correct 18 ms 14168 KB Output is correct
5 Correct 16 ms 14168 KB Output is correct
6 Correct 17 ms 14168 KB Output is correct
7 Correct 38 ms 14240 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 3 ms 14168 KB Output is correct
12 Correct 3 ms 14168 KB Output is correct
13 Correct 4 ms 14168 KB Output is correct
14 Incorrect 3 ms 14168 KB 1st lines differ - on the 1st token, expected: '706880838', found: '106303284'
15 Halted 0 ms 0 KB -

Subtask #8
0 / 11.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 17 ms 14168 KB Output is correct
4 Correct 18 ms 14168 KB Output is correct
5 Correct 16 ms 14168 KB Output is correct
6 Correct 17 ms 14168 KB Output is correct
7 Correct 38 ms 14240 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 3 ms 14168 KB Output is correct
12 Correct 3 ms 14168 KB Output is correct
13 Correct 4 ms 14168 KB Output is correct
14 Incorrect 3 ms 14168 KB 1st lines differ - on the 1st token, expected: '706880838', found: '106303284'
15 Halted 0 ms 0 KB -