QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#247482#7738. Equivalent RewritingRedcrown#WA 0ms20056kbC++171.7kb2023-11-11 14:35:412023-11-11 14:35:42

Judging History

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

  • [2023-11-11 14:35:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:20056kb
  • [2023-11-11 14:35:41]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ssz(x) ((int)x.size())
using namespace std;
const int N=3e5+5;
int n,m;
inline int red(){
	int data=0;bool w=0;char ch=getchar();
	while(ch!='-' && (ch<'0' || ch>'9'))ch=getchar();
	if(ch=='-') w=1,ch=getchar();
	while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
	return w?-data:data;
}
vector <int> op[N];
vector <int> G[N];
int du[N],num,pos;
void add(int a,int b){
	G[a].push_back(b);
	++du[b];
}
int ans[N],top;
void solve(){
	n=red();m=red();
	top=0;
	for(int i=1;i<=max(n,m);i++){
		op[i].clear();du[i]=0;G[i].clear();
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&num);
		for(int j=1;j<=num;j++){
			scanf("%d",&pos);
			op[pos].push_back(i);
		}
	}
	for(int i=1;i<=m;i++){
		int last=-1;
		for(auto v:op[i]){
			if(last==-1){
				last=v;
			}else{
				add(last,v);
				last=v;
			}
		}
	}
	queue <int> Q;
	for(int i=1;i<=n;i++){
		if(!du[i]){
			Q.push(i);
		}
	}
	int flag=0;
	while(!Q.empty()){
		if(!flag&&Q.size()>=2){
			int a=Q.front();Q.pop();
			int b=Q.front();Q.pop();
			Q.push(max(a,b));Q.push(min(a,b));
			flag=1;
		}
		int a=Q.front();Q.pop();
		ans[++top]=a;
		for(auto v:G[a]){
			--du[v];
			if(!du[v]){
				Q.push(v);
			}
		}
	}
	if(!flag){
		printf("No\n");
	}else{
		printf("Yes\n");
		for(int i=1;i<=n;i++){
			printf("%d%c",ans[i]," \n"[i==n]);
		}	
	}
}
int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0); 
	int T=1;
	T=red();
	while(T--)solve();
	return 0;
}
/*
  4
  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
  3 2
  2 1 2
  1 1
  1 2
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 18372kb

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
No
No

result:

ok OK. (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 20056kb

input:

1
10 5
2 2 4
4 1 3 4 2
1 2
3 2 1 4
4 5 2 4 3
3 2 5 4
3 5 4 2
3 1 3 2
5 1 4 2 3 5
1 4

output:

No

result:

wrong answer jury found an answer but participant did not (test case 1)