80分MLE求助

P1983 [NOIP2013 普及组] 车站分级

Dreamlands @ 2022-10-18 21:02:17

RT,奇奇怪怪的错误

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m,s[1010],t,rec_1,last,maxx,ans,rec2;
bool f[1010];
vector<int>dag[1010],ser2,G;
queue<int>ser1;
inline int read() {
    int X=0;
    bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') {
            f=1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        X=(X<<1)+(X<<3)+ch-'0';
        ch=getchar();
    }
    if(f==1) {
        return ~(X-1);
    } else {
        return X;
    }
}
int main() {

    n=read(),m=read();
    for(register int i=1; i<=m; i++) {
        t=read();
        last=read();
        ser1.push(last);
        for(register int j=2; j<=t; j++) {
            rec_1=read();
            ser1.push(rec_1);
            for(register int k=last+1; k<rec_1; k++) {
                ser2.push_back(k);
            }
            last=rec_1;
        }
        for(register int j=0; j<ser1.size(); j++) {
            for(register int k=0; k<ser2.size(); k++) {
                dag[ser1.front()].push_back(ser2[k]);
//              printf("Line %d:%d->%d\n",j+1,ser1.front(),ser2[k]);
                s[ser2[k]]++;
            }
            ser1.pop();
            j--;
        }
        ser2.clear();
    }
    rec2=n+1;
    for(register int i=1; i<=n; i++) {
        if(s[i]==0) {
            rec2--;
        }
    }
    bool f114514=0,f2=0;
    ser2.clear();
    for(register int k=1; k<=n; k++) {
        f114514=0,f2=0;
        for(register int i=1; i<=n; i++) {
            if(s[i]!=-1) {
                f2=1;
            }
            if(s[i]==0) {
//              printf("Line #:%d释放\n",i);
                f114514=1;
//              printf("Line *:%d\nLine !:",i);
                for(register int j=0; j<dag[i].size(); j++) {
//                  s[dag[i][j]]--;
                    ser2.push_back(dag[i][j]);
//                  printf("[%d,%d] ",dag[i][j],s[dag[i][j]]);
                }
//              puts("");
                dag[i].clear();
                rec2--;
                s[i]=-1;
            }
        }
        for(register int i=0; i<ser2.size(); i++) {
            s[ser2[i]]--;
        }
        ser2.clear();
        if(f114514==1) {
            ans++;
        }
        if(f2==0) {
            break;
        }
//      printf("!!! %d %d %d\n",rec2,k,ans);
        for(register int j=1; j<=n; j++) {
//          printf("%d ",s[j]);
        }
//      puts("");
    }
    printf("%d",ans);
    return 0;
}

by Dreamlands @ 2022-10-20 18:32:03

警示后人,不要用vector,因为倍增


by lalaouye @ 2022-10-27 21:12:43

可以用,需要判断重边


by lalaouye @ 2022-10-27 21:13:04

@Dreamlands


by Dreamlands @ 2022-10-30 08:58:42

@lalaouye123 细说


by lalaouye @ 2022-10-30 09:00:34

@Dreamlands 就是我在建边时判断了一下,如果两两之间已经有边了那就不用再建边了


by Dreamlands @ 2022-10-30 09:03:17

@lalaouye123 okkk,谢谢大佬


by cxlian25 @ 2023-01-06 14:43:42

@Dreamlands 什么意思啊,我也用邻接表mle了


|