C++MLE求助,玄关
查看原帖
C++MLE求助,玄关
1048193
PengDave楼主2024/3/3 22:27

不是说不加虚点优化能过吗?

#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#define mp make_pair
using namespace std;
typedef pair<short,short> pii;
vector<short> g[1010];
int in[1010];
int tmp[1010];
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,m;int si;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>si;
		bitset<1005> vis;
		for(int j=1;j<=si;j++){
			cin>>tmp[j];
			vis[tmp[j]]=1;
		}
		for(int j=1;j<=si;j++){
			for(int k=tmp[1]+1;k<tmp[si];k++){
				if(!vis[k]){
					g[tmp[j]].push_back(k);
					in[k]++;
				}
			}
		}
	}
	queue<pii> q;
	for(int i=1;i<=n;i++){
		if(!in[i]){
			q.push(mp(i,1));
		}
	}
	short ans=0;
	while(!q.empty()){
		short u=q.front().first;
		short k=q.front().second;
		q.pop();
		ans=max(ans,k);
		for(short i:g[u]){
			in[i]--;
			if(!in[i]){
				q.push(mp(i,k+1));
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
2024/3/3 22:27
加载中...