Submission #1127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127		gs12117	Synchronization (JOI13_synchronization)	C++98	60 / 100	952 ms	18580 KiB

synchronization

#include<stdio.h>
int edge[100100][2];
int root[100100];
int elist[200100];
int es[100100];
int echg[200100];
int query[100100];
int n,m,q;
int chk[100100];
int echk[100100];
int vchk[100100];
int its[1<<19];
int ite[1<<19];
int ifs[1<<19];
int ife[1<<19];
int total[1<<19];
int calc(int loc,int *it){
	loc+=7;
	int i;
	int ans=0;
	for(i=0;i<18;i++){
		if(loc&(1<<i)){
			ans+=it[loc];
			loc-=1<<i;
		}
	}
	return ans;
}
void push(int loc,int k,int *it){
	loc+=7;
	int i;
	for(i=0;i<18;i++){
		if(loc&(1<<i)){
			it[loc]+=k;
			loc+=1<<i;
		}
	}
}
void ins(int start,int end,int k,int *it){
	push(start,k,it);
	push(end+1,-k,it);
}
int ssc(int val,int *it){
	int i;
	int loc=-1;
	for(i=17;i>=0;i--){
		loc+=(1<<i);
		if(calc(loc,it)>=val)loc-=(1<<i);
	}
	loc++;
	return loc;
}
int msc(int val,int *it){
	int i;
	int loc=-1;
	for(i=17;i>=0;i--){
		loc+=(1<<i);
		if(calc(loc,it)>val)loc-=(1<<i);
	}
	return loc;
}
void dfs(int loc){
	chk[loc]=1;
	int i;
	for(i=es[loc];i<es[loc+1];i++){
		if(chk[elist[i]]==0){
			root[elist[i]]=loc;
			dfs(elist[i]);
		}
	}
}
void vdfs(int loc){
	vchk[loc]=1;
	int i;
	for(i=es[loc];i<es[loc+1];i++){
		if(vchk[elist[i]]==0&&echk[elist[i]]==1){
			vdfs(elist[i]);
		}
	}
}
int main(){
	int i;
	scanf("%d%d%d",&n,&m,&q);
	for(i=0;i<n-1;i++){
		scanf("%d%d",&edge[i][0],&edge[i][1]);
	}
	for(i=0;i<m;i++){
		scanf("%d",&echg[i]);
	}
	for(i=0;i<q;i++){
		scanf("%d",&query[i]);
	}
	if(q==1){
		for(i=0;i<m;i++){
			echg[i]--;
		}
		for(i=0;i<n-1;i++){
			es[edge[i][0]+2]++;
			es[edge[i][1]+2]++;
		}
		for(i=0;i<n+3;i++){
			es[i+1]+=es[i];
		}
		for(i=0;i<n-1;i++){
			elist[es[edge[i][0]+1]]=edge[i][1];
			elist[es[edge[i][1]+1]]=edge[i][0];
			es[edge[i][0]+1]++;
			es[edge[i][1]+1]++;
		}
		dfs(query[0]);
		for(i=0;i<m;i++){
			if(edge[echg[i]][0]==root[edge[echg[i]][1]]){
				echg[i]=edge[echg[i]][1];
			}
			else{
				echg[i]=edge[echg[i]][0];
			}
		}
		for(i=0;i<m;i++){
			echk[echg[i]]++;
			echk[echg[i]]%=2;
		}
		vdfs(query[0]);
		for(i=m-1;i>=0;i--){
			echk[echg[i]]++;
			echk[echg[i]]%=2;
			if(echk[echg[i]]==1&&vchk[root[echg[i]]]==1&&vchk[echg[i]]==0){
				vdfs(echg[i]);
			}
		}
		int ans=0;
		for(i=1;i<=n;i++){
			if(vchk[i]==1){
				ans++;
			}
		}
		printf("%d",ans);
		return 0;
	}
	else{
		for(i=1;i<=n;i++){
			push(i,1,its);
			push(i,1,ite);
			push(i,1,ifs);
			push(i,1,ife);
		}
		for(i=0;i<m;i++){
			echk[echg[i]]++;
			echk[echg[i]]%=2;
			if(echk[echg[i]]==1){
				ins(ssc(echg[i],ife),msc(echg[i],ife),calc(echg[i]+1,ite)-echg[i],ife);
				ins(ssc(echg[i]+1,ifs),msc(echg[i]+1,ifs),calc(echg[i],its)-(echg[i]+1),ifs);
				ins(calc(echg[i],its),echg[i],calc(echg[i]+1,ite)-echg[i],ite);
				ins(echg[i]+1,calc(echg[i]+1,ite),calc(echg[i],its)-(echg[i]+1),its);
			}
			else{
				ins(calc(echg[i],its),echg[i],echg[i]-calc(echg[i],ite),ite);
				ins(echg[i]+1,calc(echg[i]+1,ite),echg[i]+1-calc(echg[i]+1,its),its);
			}
		}
		for(i=1;i<=n;i++){
			ins(calc(i,ifs),calc(i,ife),1,total);
		}
		for(i=0;i<q;i++){
			printf("%d\n",calc(query[i],total));
		}
		return 0;
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40