QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#258326#7738. Equivalent Rewritingqyh619718WA 3ms13040kbC++141.5kb2023-11-19 17:07:072023-11-19 17:07:07

Judging History

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

  • [2023-11-19 17:07:07]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:13040kb
  • [2023-11-19 17:07:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

const int N = 2e5 + 7, M = 2e5 + 7;

int n, m, res, siz[N], last[N], deg[N], ans[N], cnt;
vector<int>mp[M], mp2[M];
queue<int>q;
void init()
{
	cin >> n >> m, cnt = 0;
	for (int i = 1; i <= n; i++) mp[i].clear(), mp2[i].clear(), siz[i] = 0, deg[i] = 0;
	for (int i = 1; i <= m; i++) last[i] = 0;
}
signed main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--)
	{
		for (int i = 1; i <= n; i++)
		{
			cin >> siz[i];
			for (int j = 1; j <= siz[i]; j++)
			{
				cin >> res;
				last[res] = i;
				mp2[i].push_back(res);
			}
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < siz[i]; j++)
			{
				int nx = last[mp2[i][j]];
				if (last[mp2[i][j]] != i)
				{
					mp[i].push_back(nx);
					deg[nx]++;
				}
			}
		}
		for (int i = n; i >= 1; i--) if (deg[i] == 0) q.push(i);
		for (int i = 1; i <= n; i++) sort(mp[i].begin(), mp[i].end()), reverse(mp[i].begin(), mp[i].end());
		while (q.size())
		{
			int x = q.front();
			q.pop();
			ans[++cnt] = x;
			for (int i = 0; i < (int)mp[x].size(); i++)
			{
				int nx = mp[x][i];
				deg[nx]--;
				if (deg[nx] == 0) q.push(nx);
			}
		}
		int flag = 0;
		for (int i = 1; i <= n; i++) if (ans[i] != i) flag = 1;
		if (flag)
		{
			cout << "Yes"<<endl;
			for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
			cout<<endl;
		}
		else cout << "No"<<endl;;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 13040kb

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:

No
No
No

result:

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