QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#548104#7738. Equivalent RewritingmmzskmWA 2ms12256kbC++172.0kb2024-09-05 15:29:572024-09-05 15:29:58

Judging History

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

  • [2024-09-05 15:29:58]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12256kb
  • [2024-09-05 15:29:57]
  • 提交

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)