QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379178#7738. Equivalent Rewritingucup-team3294#WA 0ms3544kbC++231.2kb2024-04-06 16:30:292024-04-06 16:30:29

Judging History

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

  • [2024-04-06 16:30:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3544kb
  • [2024-04-06 16:30:29]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=5e3+5;
const int M=1e4+5;
void solve() {
	int n,m;
	cin>>n>>m;
	vector<int> G[n+1],in(n+1),vis[m+1];
	for(int i=1;i<=n;i++){
		int k;
		cin>>k;
		while(k--){
			int x;
			cin>>x;
			vis[x].push_back(i);
		}
	}
	for(int i=1;i<=m;i++){
		if(vis[i].size()==0) continue;
		if(vis[i][0]==vis[i][vis[i].size()-1]) continue;
		G[vis[i][0]].push_back(vis[i][vis[i].size()-1]);
		in[vis[i][vis[i].size()-1]]++;
	}
	vector<int> ans;
	priority_queue<int> q;
	for(int i=n;i>=1;i--){
		if(!in[i]){
			q.push(i);
		}
	}
	while(q.size()){
		int u=q.top();
		ans.push_back(u);
		q.pop();
		for(auto v:G[u]){
			in[v]--;
			if(in[v]==0){
				q.push(v);
			}
		}
	}
	bool yt=0;
	int t=1;
	for(auto x:ans){
		if(x!=t){
			yt=1;
			break;
		}
		t++;
	}
	if(!yt){
		cout<<"No\n";
	}else{
		cout<<"Yes\n";
		for(int i=0;i<ans.size();i++){
			if(i) cout<<" "<<ans[i];
			else cout<<ans[i];
		}
		cout<<"\n";
	}
}
signed main() {
	int T=1;
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3544kb

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:

Yes
8 7 6 5 4 3 2 1 10 9

result:

wrong answer two transactions are not equivalent. (test case 1)