QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424744#7738. Equivalent RewritingijisooWA 0ms5936kbC++142.4kb2024-05-29 16:33:002024-05-29 16:33:01

Judging History

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

  • [2024-05-29 16:33:01]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5936kb
  • [2024-05-29 16:33:00]
  • 提交

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;//
int temp;
int jishu;
priority_queue<int>bb;
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()
{
	flag=0;
	prin.clear();
	aa.clear();
	edge.clear();
	memset(lastbian,0,sizeof(lastbian));
	memset(head,-1,sizeof(head));
	memset(ru,0,sizeof(ru));
	while(!bb.empty())
	{
		bb.pop();
	}
//	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()
{
	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()
{
	cout<<m<<"m";
	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 (temp==56035&&jishu==17)
	{
		for (int i=1;i<=m;i++)
		{
			cout<<lastbian[i]<<" ";
		}
	} 
	for (int i=0;i<aa.size();i++)
	{
		op it=aa[i];
		if (lastbian[it.index]!=it.biancheng)
		{
			if (temp==56035&&jishu==17)
			{
				cout<<it.biancheng<<" "<<lastbian[it.index];
			} 
			add(it.biancheng,lastbian[it.index]);
		}
	}
	if (temp==56035&&jishu==17)
	{
		for (int i=1;i<=n;i++)
		{
			cout<<ru[i]<<" ";
		}
	}
	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;
	temp=T; 
	while(T--)
	{
		jishu++;
		cin>>n>>m;
		init();
		if (n==1)
		{
			cout<<"No\n";
			continue;
		}
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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:

6mYes
3 1 2
3mNo
No

result:

wrong answer Token parameter [name=yesno] equals to "6mYes", doesn't correspond to pattern "Yes|No" (test case 1)