求助,声明顺序为什么会影响#7结果?

P3806 【模板】点分治 1

yangyi2120 @ 2021-03-02 20:48:12

下面的代码提交后会在#7发生RE:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 100010
#define inf 10000000
#define re register
using namespace std;
inline int read()
{
    int p=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())
        if(ch=='-') f*=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())
        p=p*10+ch-48;
    return p*f;
}
struct node{
    int v;
    int dis;
    int next;
}edge[maxn<<1];
int m,n,root,sum;
int tot;//used in function add(),primarily 0
int st[maxn];//st[u]==the arraymarks of an edge whose tail is vertex u which was the last to be input
int mroot[maxn];//mroot[i]==max size of child tree when the root is vertex i
int size[maxn];
int vis[maxn];//to store whether the vertex has been visited
int nowd[maxn];
int dis[maxn];
int q[maxn];
int judge[inf];
int lans[inf];//answers
int query[1010];
void add(int u,int v,int dis)
{
    edge[++tot].next=st[u];//store the last edge whose tail is vertex u
    edge[tot].v=v;//the head of the edge
    edge[tot].dis=dis;
    st[u]=tot;//renew st[u]
}
void getroot(int u,int pa)//"pa" means "parent"
{
    size[u]=1;//pa下u为根的子树大小 
    mroot[u]=0;
    for(re int i=st[u];i;i=edge[i].next)
    {
        re int v=edge[i].v;
        if(v==pa||vis[v])
            continue;
        getroot(v,u);
        size[u]+=size[v];
        mroot[u]=max(mroot[u],size[v]);
    }
    mroot[u]=max(mroot[u],sum-size[u]);
    if(mroot[u]<mroot[root])
        root=u;
}
void getdis(int u,int fa)
{
    nowd[++nowd[0]]=dis[u];
    for(re int i=st[u];i;i=edge[i].next)
    {
        re int v=edge[i].v;
        if(v==fa||vis[v])
            continue;
        dis[v]=dis[u]+edge[i].dis;
        getdis(v,u);
    }
}
void calc(int u)
{
    re int p=0;
    for(re int i=st[u];i;i=edge[i].next)
    {
        re int v=edge[i].v;
        if(vis[v])
            continue;
        nowd[0]=0;
        dis[v]=edge[i].dis;
        getdis(v,u);
        for(re int j=nowd[0];j;--j)
            for(re int k=1;k<=m;++k)
                if(query[k]>=nowd[j])
                    lans[k]|=judge[query[k]-nowd[j]];
        for(re int j=nowd[0];j;--j)//this comes after the queries so the answers in which the vertexes are both in one child tree are excluded
        {
            q[++p]=nowd[j];
            judge[nowd[j]]=1;
        }
    }
    for(re int i=1;i<=p;++i)
        judge[q[i]]=0;
}
void solve(int u)
{
    vis[u]=judge[0]=1;
    calc(u);
    for(re int i=st[u];i;i=edge[i].next)
    {
        re int v=edge[i].v;
        if(vis[v])
            continue;
        sum=size[v];
        mroot[root=0]=inf;
        getroot(v,0);
        solve(root);
    }
}
int main(void)
{
    n=read();
    m=read();
    for(re int i=1;i<n;++i)
    {
        re int u=read(),v=read(),dis=read();
        add(u,v,dis);
        add(v,u,dis);
    }
    for(re int i=1;i<=m;++i)
        query[i]=read();
    mroot[root]=sum=n;//root is currently zero
    getroot(1,0);//find the root of the whole tree
    solve(root);//root is currently zero
    for(re int i=1;i<=m;++i)
    {
        if(lans[i])
            printf("AYE\n");
        else
            printf("NAY\n");
    }
    return 0;
}

其中有一段声明:

int m,n,root,sum;
int tot;//used in function add(),primarily 0
int st[maxn];//st[u]==the arraymarks of an edge whose tail is vertex u which was the last to be input
int mroot[maxn];//mroot[i]==max size of child tree when the root is vertex i
int size[maxn];
int vis[maxn];//to store whether the vertex has been visited
int nowd[maxn];
int dis[maxn];
int q[maxn];
int judge[inf];
int lans[inf];//answers
int query[1010];

在我把这段声明改为下面这段之后,代码就可以通过了:

int m,n,tot,root,sum;//used in function add(),primarily 0
int st[maxn];//st[u]==the arraymarks of an edge whose tail is vertex u which was the last to be input
int mroot[maxn];//mroot[i]==max size of child tree when the root is vertex i
int size[maxn];
int dis[maxn];
int nowd[maxn];
int vis[maxn];//to store whether the vertex has been visited
int q[maxn];
int lans[inf];//answers
int judge[inf];
int query[1010];//suspect reserved

但是,这两段声明的唯一不同之处就是声明的顺序不同,而且仅仅是int型变量之间、大小相同的int型数组之间的顺序不同,提交结果就不一样。鄙人想了很久、做了很多次实验都没能发现其中的奥秘,所以就来请教诸位的高见。


by cmll02 @ 2021-03-02 20:58:23

盲猜数组太小


by BlankAo @ 2021-03-02 22:25:46

@yangyi2120

您的inf是10000000,也就意味着数组下标是0~inf-1。 lans[k]|=judge[query[k]-nowd[j]];

judge[nowd[j]]=1;

在这些语句中,你的下标可能达到inf,这样会导致数组越界,所以会RE。

至于调整顺序后AC,可能是因为越界后正巧越界到了一个没有用到的内存,所以是正常的。

建议改成inf=10000123


|