QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317057#7738. Equivalent RewritingPZhengWA 0ms3640kbC++141.5kb2024-01-28 13:43:022024-01-28 13:43:02

Judging History

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

  • [2024-01-28 13:43:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3640kb
  • [2024-01-28 13:43:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
bool cmp(int x, int y) {
	return x > y;
}
struct dag
{
	int n;
	vector<vector<int>> e;
	vector<int> in, vis, dp;
	dag(int n) : n(n) {
		e.resize(n + 1);
		in.resize(n + 1);
		vis.resize(n + 1);
		dp.resize(n + 1);
	}
	void add(int u, int v) {
		e[u].push_back(v);
		in[v]++;
	}
	void init() {
		for(int u = 1; u <= n; u++) {
			sort(e[u].begin(),e[u].end(), cmp);
		}
	}
	bool topo(vector<int>& ans) {
		int cnt = 0;
		bool ok = 0;
		priority_queue<int> q;
		for(int i = n; i >= 1; i--) {
			if(!in[i]) {
				ans.push_back(i);
				q.push(i);
				if(++cnt != i) {
					ok = 1;
				}
			}
		}
		while(!q.empty()) {
			int u = q.top();
			q.pop();
			for(int v : e[u]) {
				in[v]--;
				if(!in[v]) {
					ans.push_back(v);
					q.push(v);
					if(v != ++cnt) {
						ok = 1;
					}
				}
			}
			if(cnt == n) {
				return ok;
			}
		}
		return 0;
	}
};
void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(m + 1);
	for(int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		while(p--) {
			int x;
			cin >> x;
			a[x].push_back(i);
		}
	}
	dag da(n);
	for(int i = 1; i <= m; i++) {
		for(int j = 1; j < a[i].size(); j++){
			da.add(a[i][j - 1], a[i][j]);
		}
	}
	da.init();
	vector<int> ans;
	if(da.topo(ans)) {
		cout << "Yes" << endl;
		for(int u : ans) {
			cout << u << ' ';
		}
		cout << endl;
	}
	else {
		cout << "No" << endl;
	}
}
int main() {
	int t;
	cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

详细

Test #1:

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

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

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)