oj.uz

Submission #1127

# Submission time Handle Problem Language Result Execution time Memory
1127 2013-06-26T08:12:24 Z gs12117 Synchronization (JOI13_synchronization) C++
60 / 100
 952 ms 18580 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15816 KB Output is correct
2 Correct 0 ms 15816 KB Output is correct
3 Correct 0 ms 15816 KB Output is correct
4 Correct 0 ms 15816 KB Output is correct
5 Correct 0 ms 15816 KB Output is correct
6 Correct 0 ms 15816 KB Output is correct
7 Correct 6 ms 15816 KB Output is correct
8 Correct 4 ms 15816 KB Output is correct
9 Correct 5 ms 15816 KB Output is correct
10 Correct 66 ms 15816 KB Output is correct
11 Correct 75 ms 15816 KB Output is correct
12 Correct 64 ms 17536 KB Output is correct
13 Correct 60 ms 15816 KB Output is correct
14 Correct 55 ms 15816 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 17304 KB Output is correct
2 Correct 59 ms 16584 KB Output is correct
3 Correct 44 ms 18580 KB Output is correct
4 Correct 46 ms 18180 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15816 KB Output is correct
2 Correct 0 ms 15816 KB Output is correct
3 Correct 0 ms 15816 KB Output is correct
4 Correct 0 ms 15816 KB Output is correct
5 Correct 0 ms 15816 KB Output is correct
6 Correct 6 ms 15816 KB Output is correct
7 Correct 85 ms 15816 KB Output is correct
8 Correct 947 ms 15816 KB Output is correct
9 Correct 943 ms 15816 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 15816 KB Output is correct
2 Correct 532 ms 15816 KB Output is correct
3 Correct 528 ms 15816 KB Output is correct
4 Correct 525 ms 15816 KB Output is correct

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 15816 KB Output isn't correct
2 Halted 0 ms 0 KB -
3 Halted 0 ms 0 KB -
4 Halted 0 ms 0 KB -
5 Halted 0 ms 0 KB -
6 Halted 0 ms 0 KB -
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -