求助大佬,这题为啥MLE了两个点???

P1983 [NOIP2013 普及组] 车站分级

有朋自远方来 @ 2019-07-20 10:29:24

RT

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

int ans=1,n,m,ru[1005],s[1005][1005],vis[1005];
vector<int> f[1005];
queue<pair<int,int> > q; 

void BFS()
{
    for(int i=1;i<=n;i++)//i<=m
    {
        if(ru[i]==0)  q.push(make_pair(i,1));
    }
    while(q.size())
    {
        pair<int,int> a=q.front();q.pop();
        int x=a.first,y=a.second;
        for(int i=0;i<f[x].size();i++)
        {
            ru[f[x][i]]--;
            if(ru[f[x][i]]==0)
            {
                q.push(make_pair(f[x][i],y+1));
                ans=max(ans,y+1);
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        memset(vis,0,sizeof(vis));
        cin>>s[i][0];
        for(int j=1;j<=s[i][0];j++)
        {
            cin>>s[i][j];
            vis[s[i][j]]=1; 
        }
        for(int j=s[i][1];j<=s[i][s[i][0]];j++)//j=1;  xxx
        {
            if(vis[j])  continue;
            for(int k=1;k<=s[i][0];k++)
            {
                    f[j].push_back(s[i][k]);//s[i][j]
                    ru[s[i][k]]++;//i,j
            }
        }
    }

    BFS();

    cout<<ans<<endl;

    return 0;
}

by 季之怡 @ 2019-07-23 16:05:20

@有朋自远方来 想下一个测试点

/*
1000 1000
500 1 {中间498个数} 100
。。。。。。。。{下面有999行一样的}

 */

王炸


by 有朋自远方来 @ 2019-07-23 16:26:09

@季之怡 哦,谢谢,过掉了


|