关于MLE
查看原帖
关于MLE
149219
_mazetorches楼主2020/9/1 23:16

这道题下面有一大段,讲述关于怎么样会MLE,怎么避免MLE。但我们老师说,这些东西在平时评测时不会出现。

于是我信心满满地交了一份DFS部分分代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,s[30000],f[30000],ti[30000],ton[30000],d[30000],p[30000];
int to[30000*2],st[30000*2],nx[30000*2],tot;
void add(int u,int v){
	to[++tot]=v;
	nx[tot]=st[u];
	st[u]=tot;
}
void dfs(int u,int fa){
	for(int i=st[u];i;i=nx[i]){
		int v=to[i];
		if(v==fa) continue;
		p[v]=u;
		d[v]=d[u]+1;
		dfs(v,u);
	}
}
void dfs1(int u,int fin,int time){
//	cout<<"$$$ "<<u<<' '<<fin<<' '<<time<<endl;
	if(ti[u]==time){
		ton[u]++;
	}
	if(u==fin){
		return;
	}
	dfs1(p[u],fin,time+1);
}
void dfs2(int u,int fin,int time){
//	cout<<"$$$ "<<u<<' '<<fin<<' '<<time<<endl;
	if(ti[u]==time){
		ton[u]++;
	}
	if(u==fin){
		return;
	}
	dfs2(p[u],fin,time-1);
}
bool dfs4(int u,int fin){
	if(u==fin){
		return 1;
	}
	if(u==1){
		return 0;
	}
	return dfs4(p[u],fin);
}
int main(){
//	freopen("running.in","r",stdin);
//	freopen("running.out","w",stdout);
//	cout<<pow(2,0);
	cin>>n>>m;
	int u,v;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++){
		cin>>ti[i];
	}
	for(int i=1;i<=m;i++){
		cin>>s[i]>>f[i];
	}
	dfs(1,-1);
	for(int i=1;i<=m;i++){
		if(dfs4(s[i],f[i])==0&&dfs4(f[i],s[i])==0){
			int bef=ton[1];
			dfs1(s[i],1,0);
			if(ton[1]!=bef) ton[1]--;
			dfs2(f[i],1,d[f[i]]+d[s[i]]);
		}
		else{
			if(d[s[i]]>d[f[i]]) dfs1(s[i],f[i],0);
			else dfs2(f[i],s[i],d[f[i]]-d[s[i]]);
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ton[i]<<' ';
	}
//	}
}

但很奇怪,MLE了。

所以有大佬为我说一下这是为什么吗?

2020/9/1 23:16
加载中...