关于MLE

P1600 [NOIP2016 提高组] 天天爱跑步

_maze @ 2020-09-01 23:16:58

这道题下面有一大段,讲述关于怎么样会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了。

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


by eaten_apple @ 2020-09-09 21:05:17

好孤寂啊


|