QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#548104 | #7738. Equivalent Rewriting | mmzskm | WA | 2ms | 12256kb | C++17 | 2.0kb | 2024-09-05 15:29:57 | 2024-09-05 15:29:58 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
int n, m, idx, cnt;
int to[mxn], nxt[mxn], head[mxn], indegree[mxn], ans[mxn];
vector<vector<int>> p;
void init()
{
fill(head, head + m + 1, 0);
fill(indegree, indegree + m + 1, 0);
p.clear();
p.resize(m + 1);
idx = cnt = 0;
}
void add(int u, int v)
{
to[++idx] = v;
nxt[idx] = head[u];
head[u] = idx;
}
void toposort()
{
queue<int> q;
for (int i = 1; i <= n; i++)
{
if (!indegree[i])
{
q.push(i);
}
}
while (q.size())
{
int u = q.front();
q.pop();
ans[++cnt] = u;
for (int i = head[u]; i; i = nxt[i])
{
int v = to[i];
indegree[v]--;
if (!indegree[v])
{
q.push(v);
}
}
}
}
void solve()
{
scanf("%lld%lld", &n, &m);
init();
for (int i = 1; i <= n; i++)
{
int k;
scanf("%lld", &k);
for (int j = 1; j <= k; j++)
{
int x;
scanf("%lld", &x);
p[x].push_back(i);
}
}
for (int i = 1; i <= m; i++)
{
int sz = p[i].size();
for (int j = 0; j < sz - 1; j++)
{
add(p[i][j], p[i][sz - 1]);
indegree[p[i][sz - 1]]++;
}
}
toposort();
for (int i = 1; i <= n; i++)
{
if (ans[i] != i) // 检查跟原操作顺序是否相同
{
printf("Yes\n");
for (int i = 1; i <= n; i++)
{
printf("%lld%c", ans[i],(i == n ? '\n' : ' '));
}
return;
}
}
printf("No\n");
}
signed main()
{
int T = 1;
scanf("%lld", &T);
while (T--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12256kb
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 1 3 2 No No
result:
ok OK. (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 11988kb
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)