UVALive 3486/zoj 2615 Cells(栈模拟dfs)

时间:2021-04-22 20:18:54

这道题在LA是挂掉了,不过还好,zoj上也有这道题。

题意:好大一颗树,询问父子关系。。考虑最坏的情况,30w层,2000w个点,询问100w次,貌似连dfs一遍都会TLE。

安心啦,这肯定是一道正常人能做的题目。不过是需要几个小技巧。

1、2000w个点不一定都要保存下来,事实上,虽然题目给了256M的空间,只要开了两个这么大的数组,MLE是跑不了的,所以只保存30w个父节点。

2、如果这30w个父节点构成一条链,dfs的栈肯定爆。所以需要用栈模拟dfs。这里用的是stack<int>,当然手写栈会更快。

注意:1、时间戳的使用。

    2、本题中顺序对节点标号,使得所有>=n的节点都是叶子节点,同时能够二分也是因为它是有序的。

 #include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std; const int MAXN=; struct Point{
int l,r;
}point[MAXN]; struct T{
int in,out;
}tim[MAXN]; int child[MAXN],dfs_clock;
stack<int>stk; void init()
{
dfs_clock=;
while(!stk.empty())
stk.pop();
} void dfs(int n)
{
init();
stk.push();
tim[].in=++dfs_clock;
child[]=;
while(!stk.empty())
{
int x=stk.top();
int r=point[x].r;
if(child[x]>r||child[x]>=n){
tim[x].out=++dfs_clock;
stk.pop();
}else {
stk.push(child[x]);
tim[child[x]].in=++dfs_clock;
child[child[x]]=point[child[x]].l;
child[x]++;
}
}
} int find(int x,int n)//找父节点:利用顺序编码进行二分
{
int l=,r=n-;
while(l<r)
{ int m=l+(r-l+)/;
if(point[m].l<=x&&point[m].r>=x)
return m;
if(point[m].l>x)
r=m-;
else
l=m;
}
return l;
} int main()
{
int TT;
scanf("%d",&TT); int n;
for(int cas=;cas<=TT;cas++)
{
scanf("%d",&n);
int x,y=;
for(int i=;i<n;i++)
{
scanf("%d",&x);
point[i].l=y;
point[i].r=y+x-;
y+=x;
} dfs(n); int m,u,v,pv;
scanf("%d",&m);
printf("Case %d:\n",cas);
int flog;
for(int i=;i<m;i++)
{
flog=;
scanf("%d%d",&u,&v); if(u<n&&v<n){
if(tim[u].in<tim[v].in&&tim[u].out>tim[v].out)
flog=;
}
else if(u<n&&v>=n){//u<n漏掉了,导致RE;若u>=n,那么u就是叶子节点,不可能是父亲
pv=find(v,n);
if(tim[u].in<=tim[pv].in&&tim[u].out>=tim[pv].out)
flog=;
} if(flog)
printf("Yes\n");
else
printf("No\n");
}
if(cas!=TT)
puts("");
} return ;
}