QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424750#7738. Equivalent RewritingijisooWA 0ms3664kbC++141.8kb2024-05-29 16:42:352024-05-29 16:42:35

Judging History

你现在查看的是最新测评结果

  • [2024-05-29 16:42:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3664kb
  • [2024-05-29 16:42:35]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=100010;
int T;
int n,m;
vector<int>prin;//
typedef struct
{
	int biancheng;
	int index;
}op;
vector<op>aa;//
int lastbian[N];//
int head[N];//
int ru[N];//
int cnt;//
int flag=0;//
typedef struct
{
	int u,v;
	int next;
}bian;
vector<bian>edge;//
void add(int u,int v)
{
	edge.push_back({u,v,head[u]});
	head[u]=cnt++;
	ru[v]++;
}
void init()
{
	for (int i=1;i<=m;i++)
	{
		lastbian[i]=0;
	}
	for (int i=0;i<=n;i++)
	{
		head[i]=-1;
		ru[i]=0;
	}
	cnt=0;
}
int topsort()
{
	priority_queue<int>bb;
	for (int i=1;i<=n;i++)
	{
		if (ru[i]==0)
		{
			bb.push(i);
		}
	}
	while(!bb.empty())
	{
		int it=bb.top();
		bb.pop();
		prin.push_back(it);
		for (int j=head[it];j!=-1;j=edge[j].next)
		{
			ru[edge[j].v]--;
			if (ru[edge[j].v]==0)
			{
				bb.push(edge[j].v);
			}
		}
	}
	for (int i=0;i<prin.size();i++)
	{
		if (prin[i]!=i+1)
		{
			flag=1;
			break;
		}
	}
	if (flag==1)
	{
		return 1;
	}
	return 0;
}
void solve()
{
	for (int i=1;i<=n;i++)
	{
		int ge;
		cin>>ge;
		for (int j=1;j<=ge;j++)
		{
			int xiabiao;
			cin>>xiabiao;
			lastbian[xiabiao]=i;
			aa.push_back({i,xiabiao});
		}
	}
	if (n==1)
	{
		cout<<"No\n";
		return;
	} 
	for (int i=0;i<aa.size();i++)
	{
		op it=aa[i];
		if (lastbian[it.index]!=it.biancheng)
		{
			add(it.biancheng,lastbian[it.index]);
		}
	}

	if (topsort())
	{
		cout<<"Yes\n";
		for (int i=0;i<prin.size();i++)
		{
			cout<<prin[i];
			if (i==prin.size()-1)
			{
				cout<<"\n";
			}
			else
			{
				cout<<" "; 
			}
		}
	}
	else
	{
		cout<<"No\n";
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		init();
		solve();
	}
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3664kb

input:

3
3 6
3 3 1 5
2 5 3
2 2 6
2 3
3 1 3 2
2 3 1
1 3
2 2 1

output:

Yes
3 1 2
Yes
3 1 2
No

result:

wrong answer Integer parameter [name=q_i] equals to 3, violates the range [1, 2] (test case 2)