萌新求助
  • 板块CF1572A Book
  • 楼主wumingwei
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/10 13:27
  • 上次更新2024/4/10 17:31:04
查看原帖
萌新求助
542390
wumingwei楼主2024/4/10 13:27

样例2错误

Wrong Answer wrong answer 69th numbers differ - expected: '2', found: '1'

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int> fa[N];
int n,ru[N],maxx,ans[N];
bool book[N];
struct S
{
	int zhi;
	int ye;
};
bool operator<(S q,S p)
{
	if(q.zhi!=p.zhi)
	return q.zhi<p.zhi;
	return q.ye<p.ye;
}
priority_queue<S> q;
bool tp()
{
	int s=0;
	while(!q.empty())
	{
		int u=q.top().ye;
		int v=q.top().zhi;
		maxx=max(maxx,v);
		s++;
		q.pop();
		int len=fa[u].size();
		for(int i=0;i<len;i++)
		{
			int y=fa[u][i];
			ru[y]--;
			if(ru[y]==0)
			{
				if(y>u)
				{
					S w;
					w.ye=y;
					w.zhi=v;
					ans[y]=max(ans[y],v);
					q.push(w);
				}
				else
				{
					S w;
					w.ye=y;
					w.zhi=v+1;
					ans[y]=max(ans[y],v+1);
					q.push(w);
				}
			}
		}
	}
//	cout<<s<<endl;
	return s==n;
}
int main()
{
	ios::sync_with_stdio (0);
	cin.tie (0);
	cout.tie (0);
//	freopen("1.txt","w",stdout);
	int t;
	scanf("%d",&t);
	for(int k=1;k<=t;k++)
	{
		memset(ru,0,sizeof(ru));
		memset(ans,0,sizeof(ans));
		
		
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		fa[i].clear();
		for(int i=1;i<=n;i++)
		{
			int m;
			scanf("%d",&m);
			for(int j=1;j<=m;j++)
			{
				int x;
				scanf("%d",&x);
				fa[x].push_back(i);
				ru[i]++;
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(ru[i]==0)
			{
				S w;
				w.ye=i;
				w.zhi=1;
				ans[i]=1;
				q.push(w);
			}
		}
		if(tp())
		{
			maxx=0;
			for(int i=1;i<=n;i++)
			maxx=max(maxx,ans[i]);
			cout<<maxx<<endl;
		}
		else
		{
			cout<<-1<<endl;
		}
	}
	
	return 0;
}
2024/4/10 13:27
加载中...