求助,声明顺序为什么会影响#7结果?
查看原帖
求助,声明顺序为什么会影响#7结果?
397809
yangyi2120楼主2021/3/2 20:48

下面的代码提交后会在#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型数组之间的顺序不同,提交结果就不一样。鄙人想了很久、做了很多次实验都没能发现其中的奥秘,所以就来请教诸位的高见。

2021/3/2 20:48
加载中...