這個題目內存限制明明是512MB,為什麼vijos限制256MB

這個題目內存限制明明是512MB,為什麼vijos限制256MB

2 条评论

  • @ 2020-11-24 23:06:35

    這個題用線段樹稍有不慎就MLE了

    • @ 2020-11-25 00:14:10

      能不能恢復正常內存限制啊?真的AC不了。

    • @ 2020-11-26 23:56:41

      終於AC了

      #include <cmath>
      #include <cstdio>
      #include <cstdlib>
      #include <cstring>
      #include <algorithm>
      #include <vector>
      #include <deque>
      using namespace std;
      
      namespace dts
      {
          typedef unsigned int uint;
          const uint lgs=19;
          int cnt,maxdep;
          class tr_node
          {
              public:
                  int fa,dep=0,size,hs,top,id=0;
                  vector<int> s;
          };
          int rk[(1<<lgs)+1],inrec[(1<<lgs)+1],outrec[(1<<lgs)+1];
          tr_node tr[(1<<lgs)+1];
          void tr_dfs1(int now,int fa)
          {
              tr[now].fa=fa;
              if (now>0)
                  tr[now].dep=tr[fa].dep+1;
              maxdep=max(maxdep,tr[now].dep);
              tr[now].size=1;
              tr[now].hs=-1;
              for (int i=0;i<tr[now].s.size();i++)
                  if (tr[now].s[i]!=fa)
                  {
                      int next=tr[now].s[i];
                      tr_dfs1(next,now);
                      tr[now].size+=tr[next].size;
                      if (tr[now].hs==-1)
                          tr[now].hs=next;
                      else if (tr[tr[now].hs].size<tr[next].size)
                          tr[now].hs=next;
                  }
          }
          void tr_dfs2(int now,int top)
          {
              tr[now].top=top;
              tr[now].id=++cnt;
              inrec[now]=cnt;
              rk[cnt]=now;
              if (tr[now].hs!=-1)
              {
                  tr_dfs2(tr[now].hs,top);
                  for (int i=0;i<tr[now].s.size();i++)
                      if (tr[now].s[i]!=tr[now].fa&&tr[now].s[i]!=tr[now].hs)
                          tr_dfs2(tr[now].s[i],tr[now].s[i]);
              }
              outrec[now]=cnt;
          }
          void tr_build(int rt)
          {
              cnt=0,maxdep=0;
              tr_dfs1(rt,0);
              tr_dfs2(rt,rt);
          }
          int lca(int x,int y)
          {
              while (tr[x].top!=tr[y].top)
              {
                  if (tr[tr[x].top].dep<tr[tr[y].top].dep)
                      swap(x,y);
                  x=tr[tr[x].top].fa;
              }
              if (tr[x].dep<tr[y].dep)
                  return x;
              else
                  return y;
          }
          class segtree
          {
              public:
                  int size=0;
                  class strec
                  {
                      public:
                          int rt=-1,rtl=1,rtr=-1;
                  };
                  vector<strec> rec;
                  vector<int> fa,lc,rc,sl,sr,smid,sum,sumlz;
                  //deque<int> fa,lc,rc,sl,sr,smid,sum,sumlz;
                  void reszcl(int rec_size)
                  {
                      size=0;
                      rec.resize(rec_size);
                      /*fa.clear(),lc.clear(),rc.clear();
                      sl.clear(),sr.clear(),smid.clear();
                      sum.clear(),sumlz.clear();*/
                      fa.resize(rec_size<<3),lc.resize(rec_size<<3),rc.resize(rec_size<<3);
                      sl.resize(rec_size<<3),sr.resize(rec_size<<3),smid.resize(rec_size<<3);
                      sum.resize(rec_size<<3),sumlz.resize(rec_size<<3);
                  }
                  void set_st(int rcp,int l,int r)
                  {
                      rec[rcp].rt=-1,rec[rcp].rtl=l,rec[rcp].rtr=r;
                  }
                  int len(int now)
                  {
                      return sr[now]-sl[now]+1;
                  }
                  void update(int rcp,int now,int *pnow,int fath,int l,int r,int val)
                  {
                      /*if (now==-1||now+1>size)
                      {
                          now=size++;
                          fa.push_back(fath),lc.push_back(-1),rc.push_back(-1);
                          sum.push_back(0),sumlz.push_back(0);
                          if (now==rec[rcp].rt)
                              sl.push_back(rec[rcp].rtl),sr.push_back(rec[rcp].rtr);
                          else
                          {
                              if (lc[fa[now]]==now)
                                  sl.push_back(sl[fa[now]]),sr.push_back(smid[fa[now]]);
                              else if (rc[fa[now]]==now)
                                  sl.push_back(smid[fa[now]]+1),sr.push_back(sr[fa[now]]);
                          }
                          smid.push_back((sl[now]+sr[now])>>1);
                      }*/
                      if (now==-1||now+1>size)
                      {
                          now=size++,*pnow=now;
                          if (size>fa.size())
                          {
                              fa.resize(size,-1),lc.resize(size,-1),rc.resize(size,-1);
                              sl.resize(size,1),sr.resize(size,-1),smid.resize(size,0);
                              sum.resize(size,0),sumlz.resize(size,0);
                          }
                          fa[now]=fath,lc[now]=rc[now]=-1;
                          sum[now]=sumlz[now]=0;
                          if (now==rec[rcp].rt)
                              sl[now]=rec[rcp].rtl,sr[now]=rec[rcp].rtr;
                          else
                          {
                              if (lc[fa[now]]==now)
                                  sl[now]=sl[fa[now]],sr[now]=smid[fa[now]];
                              else if (rc[fa[now]]==now)
                                  sl[now]=smid[fa[now]]+1,sr[now]=sr[fa[now]];
                          }
                          smid[now]=(sl[now]+sr[now])>>1;
                      }
                      if (sl[now]==l&&r==sr[now])
                      {
                          sum[now]+=len(now)*val;
                          sumlz[now]+=val;
                      }
                      else
                      {
                          if (sumlz[now]!=0)
                          {
                              update(rcp,lc[now],&lc[now],now,sl[now],smid[now],sumlz[now]);
                              update(rcp,rc[now],&rc[now],now,smid[now]+1,sr[now],sumlz[now]);
                              sumlz[now]=0;
                          }
                          if (r<=smid[now])
                              update(rcp,lc[now],&lc[now],now,l,r,val);
                          else if (smid[now]+1<=l)
                              update(rcp,rc[now],&rc[now],now,l,r,val);
                          else
                              update(rcp,lc[now],&lc[now],now,l,smid[now],val),update(rcp,rc[now],&rc[now],now,smid[now]+1,r,val);
                          sum[now]=((lc[now]==-1)?0:sum[lc[now]])+((rc[now]==-1)?0:sum[rc[now]]);
                      }
                  }
                  int ask(int rcp,int now,int l,int r)
                  {
                      if (now==-1||now+1>size)
                          return 0;
                      if (sl[now]==l&&r==sr[now])
                          return sum[now];
                      else
                      {
                          if (sumlz[now]!=0)
                          {
                              update(rcp,lc[now],&lc[now],now,sl[now],smid[now],sumlz[now]);
                              update(rcp,rc[now],&rc[now],now,smid[now]+1,sr[now],sumlz[now]);
                              sumlz[now]=0;
                          }
                          if (r<=smid[now])
                              return ask(rcp,lc[now],l,r);
                          else if (smid[now]+1<=l)
                              return ask(rcp,rc[now],l,r);
                          else
                              return ask(rcp,lc[now],l,smid[now])+ask(rcp,rc[now],smid[now]+1,r);
                      }
                  }
          };
          segtree udst;
          
          int n,m,w[(1<<lgs)+1],s[(1<<lgs)+1],t[(1<<lgs)+1],ans[(1<<lgs)+1];
          
          void main()
          {
              scanf("%d%d",&n,&m);
              for (int i=0;i<=n;i++)
                  tr[i].s.clear();
              tr[0].s.push_back(1);
              for (int i=1;i<n;i++)
              {
                  int x,y;
                  scanf("%d%d",&x,&y);
                  tr[x].s.push_back(y);
                  tr[y].s.push_back(x);
              }
              for (int i=1;i<=n;i++)
                  scanf("%d",&w[i]);
              tr_build(1);
              for (int i=1;i<=m;i++)
                  scanf("%d%d",&s[i],&t[i]);
              memset(ans,0,sizeof(ans));
              udst.reszcl(n<<1|1);
              for (int i=0;i<=(n<<1);i++)
                  udst.set_st(i,1,n);
              for (int i=1;i<=m;i++)
              {
                  int lcan=lca(s[i],t[i]),nums=tr[s[i]].dep;
                  if (tr[s[i]].id>0)
                      udst.update(nums,udst.rec[nums].rt,&udst.rec[nums].rt,-1,tr[s[i]].id,tr[s[i]].id,1);
                  if (tr[tr[lcan].fa].id>0)
                      udst.update(nums,udst.rec[nums].rt,&udst.rec[nums].rt,-1,tr[tr[lcan].fa].id,tr[tr[lcan].fa].id,-1);
              }
              for (int i=1;i<=n;i++)
              {
                  int nums=tr[i].dep+w[i];
                  ans[i]+=udst.ask(nums,udst.rec[nums].rt,inrec[i],outrec[i]);
              }
              udst.reszcl(n<<1|1);
              for (int i=0;i<=(n<<1);i++)
                  udst.set_st(i,1,n);
              for (int i=1;i<=m;i++)
              {
                  int lcan=lca(s[i],t[i]),numt=tr[s[i]].dep-(tr[lcan].dep<<1)+n;
                  if (tr[t[i]].id>0)
                      udst.update(numt,udst.rec[numt].rt,&udst.rec[numt].rt,-1,tr[t[i]].id,tr[t[i]].id,1);
                  if (tr[lcan].id>0)
                      udst.update(numt,udst.rec[numt].rt,&udst.rec[numt].rt,-1,tr[lcan].id,tr[lcan].id,-1);
              }
              for (int i=1;i<=n;i++)
              {
                  int numt=w[i]-tr[i].dep+n;
                  ans[i]+=udst.ask(numt,udst.rec[numt].rt,inrec[i],outrec[i]);
              }
              for (int i=1;i<=n;i++)
                  printf("%d ",ans[i]);
          }
      }
      
      int main()
      {
          dts::main();
      }
      
  • @ 2020-11-24 17:27:39
    1. Vijos比较严
    2. 可不可以不用繁体字
  • 1

信息

ID
2004
难度
8
分类
(无)
标签
递交数
1665
已通过
139
通过率
8%
被复制
9
上传者