Fat_Fish @ 2021-08-05 16:11:25
rt,评测记录,实在不知道哪里错了
#include<bits/stdc++.h>
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-') {
f=-1;
}
ch=getchar();
}
while(isdigit(ch)) {
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int maxn=1e3+10;
int n,m,ind[maxn],a[maxn],d[maxn],ans,P[maxn];
vector<int> g[maxn];
void topo(){
queue<int> q;
for(int i=1;i<=n;++i){
if(ind[i]==0){
q.push(i);
d[i]=1;
}
}
while(!q.empty()){
int u=q.front();q.pop();
int len=g[u].size();
for(int i=0;i<len;++i){
int v=g[u][i];
d[v]=max(d[v],d[u]+1);
--ind[v];
if(ind[v]==0){
q.push(v);
}
}
}
for(int i=1;i<=n;++i){
ans=max(ans,d[i]);
}
return;
}
signed main() {
n=read(),m=read();
while(m--){
memset(P,0,sizeof P);
int k;
k=read();
for(int i=1;i<=k;++i){
a[i]=read();
P[a[i]]=1;
}
for(int i=a[1];i<=a[k];++i){
if(P[i]==0){
continue;
}
for(int j=i+1;j<=a[k];++j){
if(P[j]==0){
g[j].push_back(i);//j比i小
++ind[i];
}
}
}
}
topo();
printf("%d\n",ans);
return 0;
}
by Sudohry @ 2021-08-05 16:16:49
MLE也许是因为连边太多vector出问题了吧
换邻接表试一下?
by Fat_Fish @ 2021-08-05 16:18:06
可是还有WA的几个点,不知道是怎么回事QAQ
by Fat_Fish @ 2021-08-05 16:28:16
原来是我题目没看清,谢谢大佬
by Sudohry @ 2021-08-05 16:30:28
@Fat_Fish 哦我想起来了你那个MLE可能是有重边,记得判重(我也是vector党)
wa我还没看出来
by Fat_Fish @ 2021-08-05 16:36:07
没事,WA已经改了,谢谢
by Fat_Fish @ 2021-08-05 16:37:27
已经AC了