,萌新求助,为何我10w的dfs会爆掉

P1600 [NOIP2016 提高组] 天天爱跑步

ComplexPug @ 2018-09-18 19:25:16

造的一组10w的链子 dfs求deep 4w多点就结束了、、、

#include <bits/stdc++.h>
using namespace std;
const int maxn=300000;
const int maxn_25=1000;
struct edge {
    int v,nxt;
}e[maxn<<1];
int head[maxn<<1],tot;
int tim[maxn],n,m,S[maxn],T[maxn],deep[maxn<<1];

//int pd_25,ans_25[maxn_25]; //baoli 25  zhuanyong

// int tot_a,a_c[maxn<<1],find_a[maxn],ans_c[maxn];//all s == 1 zhuanyong
// int vis[maxn<<1];
// int cf[maxn<<1];

void add_edge(int u,int v)  {
    e[++tot].v=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
inline int read() {
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9') 
     {if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9') 
     {x=(x<<3)+(x<<1)+s-'0',s=getchar();}
    return x*f;
}
// void dfs_25(int u,int f,int end,int cnt) {
//  if(u==end) {
//      if(cnt==tim[u]) ans_25[u]++;
//      pd_25=1;
//      return;
//  }
//  if(pd_25) return;
//  if(cnt==tim[u]) ans_25[u]++;
//  for(int i=head[u];i;i=e[i].nxt) {
//      int v=e[i].v;
//      if(v==f) continue;
//      dfs_25(v,u,end,cnt+1);
//      if(pd_25) return;
//  }
//  if(cnt==tim[u]) ans_25[u]--;
//}
void dfs_deep(int u,int f,int cnt) {
    deep[u]=cnt;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        cout<<cnt<<"\n";
        if(f==v) continue;
        dfs_deep(v,u,cnt+1);
    }
}
// void dfs_xu(int u,int f) {
//   a_c[++tot_a]=0;
//   find_a[u]=tot_a;
//   for(int i=head[u];i;i=e[i].nxt) {
//      int v=e[i].v;
//      if(v==f) continue;
//      dfs_xu(v,u);
//   }
//   a_c[++tot_a]=0;
//   vis[tot_a]=1;
// }
int main() {
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<n;++i) {
        int x=read(),y=read();
        add_edge(x,y);
        add_edge(y,x);
    }
    for(int i=1;i<=n;++i)
        tim[i]=read();
    for(int i=1;i<=m;++i)
        S[i]=read(),T[i]=read();

    //baoli_25
    // if(n<=1000) {
    //  for(int i=1;i<=m;++i) {
    //      pd_25=0;
    //      dfs_25(S[i],0,T[i],0);
    //  }
    //  for(int j=1;j<=n;++j)
    //          printf("%d ",ans_25[j]);
    //  return 0;
    // }

    //all S[i]==1 fen==20
    dfs_deep(1,0,0);//1 -> i deep
    // cout<<tot;
    // dfs_xu(1,0);
    // for(int i=1;i<=tot_a;++i)
    //  cf[i]=a_c[i]-a_c[i];
    // //chafen
    // for(int i=1;i<=m;++i) {
    //  //1->i
    //  cf[find_a[S[i]]]++;
    //  cf[find_a[T[i]+1]]--;
    // }
    // //qiouhe
    // for(int i=1;i<=tot_a;++i) {
    //  if(vis[i])
    //      a_c[i]=a_c[i-1]-cf[i];  
    //  else
    //      a_c[i]=a_c[i-1]+cf[i];
    // }
    // for(int i=1;i<=n;++i) {
    //  if(deep[i]==tim[i])
    //      printf("%d ",a_c[find_a[i]]);
 //        else 
    //      printf("0 ");
    // }
    return 0;
}

by LJC00118 @ 2018-09-18 19:29:12

本地栈空间开小了吧


by shadowice1984 @ 2018-09-18 19:31:22

-Wl,--stack=10000000000


by ComplexPug @ 2018-09-18 19:43:42

@shadowice1984 IDE可以弄,Windows 10w 也爆,太rubbish了


|