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