有大神能帮忙看下,我的程序常数为什么这么大吗?

P4114 Qtree1

ysner @ 2018-03-22 21:44:34

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls now<<1
#define rs now<<1|1
#define mid (l+r>>1)
#define max(a,b) ((a>b)?a:b)
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e6+100;
int h[N],cnt,top[N],L[N],id[N],tim,f[N],d[N],son[N],sz[N],p[N],tot,n;
int w[N],t[N<<2];
char op[10];
struct Edge
{
  int to,next,id,w;
}e[N<<1];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void add(re int u,re int v,re int w)
{
  e[++cnt].to=v;e[cnt].next=h[u];e[cnt].w=w;e[cnt].id=++tot;h[u]=cnt;
  e[++cnt].to=u;e[cnt].next=h[v];e[cnt].w=w;e[cnt].id=tot;h[v]=cnt;
}
il void dfs(re int u,re int fa)
{
  for(re int i=h[u];i;i=e[i].next)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      w[v]=e[i].w;p[e[i].id]=v;
      dfs(v,u);
    }
}
il void dfs1(re int u,re int fa,re int deep)
{
  f[u]=fa;d[u]=deep;sz[u]=1;
  for(re int i=h[u];i;i=e[i].next)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs1(v,u,deep+1);
      sz[u]+=sz[v];
      if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
il void dfs2(re int u,re int up)
{
  L[u]=++tim;top[u]=up;id[tim]=u;
  if(son[u]) dfs2(son[u],up);
  for(re int i=h[u];i;i=e[i].next)
    {
      re int v=e[i].to;
      if(v==f[u]||v==son[u]) continue;
      dfs2(v,v);
    }
}
il void Update(re int now){t[now]=max(t[ls],t[rs]);}
il void Build(re int now,re int l,re int r)
{
  if(l==r)
    {
      t[now]=w[id[l]];
      return;
    }
  Build(ls,l,mid);
  Build(rs,mid+1,r);
  Update(now);
}
il void Modify(re int now,re int l,re int r,re int pos,re int w)
{
  if(l==r)
    {
      t[now]=w;
      return;
    }
  if(pos<=mid) Modify(ls,l,mid,pos,w);
  else Modify(rs,mid+1,r,pos,w);
  Update(now);
}
il int Query(re int now,re int l,re int r,re int ql,re int qr)
{
  if(ql<=l&&r<=qr) return t[now];
  re int res=-2e9;
  if(ql<=mid) res=Query(ls,l,mid,ql,qr);
  if(qr>mid) res=max(res,Query(rs,mid+1,r,ql,qr));
  return res;
}
int main()
{
  n=gi();
  fp(i,1,n-1)
    {
      re int u,v;int w;u=gi(),v=gi(),w=gi();
      add(u,v,w);
    }
  dfs(1,0);dfs1(1,0,0);dfs2(1,1);
  Build(1,1,n);
  while(19260817)
    {
      scanf("%s",op);re int x,y;
      if(op[0]=='D') break;
      x=gi();y=gi();
      if(op[0]=='C') Modify(1,1,n,L[p[x]],y);
      else if(op[0]=='Q')
    {
      if(x==y) {cout<<0<<endl;continue;}
      re int ans=-2e9;
      while(top[x]^top[y])
        {
          if(d[top[x]]<d[top[y]]) swap(x,y);
          ans=max(ans,Query(1,1,n,L[top[x]],L[x]));
          x=f[top[x]];
        }
      if(d[x]>d[y]) swap(x,y);
      ans=max(ans,Query(1,1,n,L[x]+1,L[y]));//不包括LCA(此时x为LCA)
      cout<<ans<<endl;
    }
      else break;
    }
  return 0;
}

by 用户已注销 @ 2018-09-27 20:31:44

cin cout 满天飞

还问为什么常数大。。。


|