AC55pts求助

P1983 [NOIP2013 普及组] 车站分级

chenyilai @ 2022-07-19 14:57:46

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
ll read(){
    ll s=0,w=1;char c=getchar();
    while(c<48||c>57){if(c=='-')w=-1;c=getchar();}
    while(c>47&&c<58)s=s*10+c-48,c=getchar();
    return s*w;
}
bool b[1005][1005];
ll n,m,x,y,f[1005],a[1005],rd[1005],maxx;
vector<ll>v[1005];
queue<ll>q;
int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        x=read();
        for(int j=0;j<x;j++)a[j]=read();
        for(int j=0;j<x-1;j++)
            for(int k=a[j]+1;k<a[j+1];k++){
                if(!b[k][a[0]])v[k].push_back(a[0]),rd[a[0]]++,b[k][a[0]]=1;
                if(!b[k][a[x-1]])v[k].push_back(a[x-1]),rd[a[x-1]]++,b[k][a[x-1]]=1;
            }
    }
    for(int i=1;i<=n;i++){
        f[i]=1;
        if(rd[i]==0)q.push(i);
    }
    while(!q.empty()){
        x=q.front();q.pop();
        for(int i=0;i<v[x].size();i++){
            y=v[x][i];
            rd[y]--;
            f[y]=max(f[y],f[x]+1);
            if(rd[y]==0)q.push(y);
        }
    }
    for(int i=1;i<=n;i++)maxx=max(maxx,f[i]);
    printf("%lld",maxx);
    return 0;
}

|