2615.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
const int MAXN=3000005;
const int MAXALL=20000005;
int stack[MAXN],reach[MAXN],left[MAXN],in[MAXALL],out[MAXALL];
int ci,co;
int n,m;
/*void dfs(int t)
{
	in[t]=ci++;
	int i;
	if(t<n)
	{
		for(i=left[t];i<left[t+1];i++)
		{
			dfs(i);
		}
	}
	out[t]=co++;
}
*/
void dfs()
{
	int depth=1;
	stack[depth]=0;reach[depth]=left[0];
	in[stack[depth]]=ci++;
	for(depth=1;depth>=1;)
	{
		if(stack[depth]>=n){out[stack[depth]]=co++;depth--;reach[depth]++;continue;}
		if(reach[depth]>=left[stack[depth]+1]){out[stack[depth]]=co++;depth--;reach[depth]++;continue;}
		stack[depth+1]=reach[depth];
		depth++;
		in[stack[depth]]=ci++;
		reach[depth]=left[stack[depth]];
	}
}





int main()
{
	int i,j,k;
	int T;
	int t;
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
		int b,c=0;
		printf("Case %d:\n",t);
		scanf("%d",&n);		
		for(i=0;i<n;i++)
		{
			left[i]=c+1;
			scanf("%d",&b);
			c+=b;			
		}
		left[n]=c+1;
		ci=0;co=0;
		dfs();
		scanf("%d",&m);
		for(i=1;i<=m;i++)
		{
			int s,t;
			scanf("%d%d",&s,&t);
			if(in[s]<in[t] && out[t]<out[s])printf("Yes\n");
			else printf("No\n");
		}
		if(t!=T)printf("\n");
	}
	return 0;
}