QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241496#7738. Equivalent Rewritingucup-team203#WA 1ms8712kbC++201.7kb2023-11-06 09:03:012023-11-06 09:03:01

Judging History

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

  • [2023-11-06 09:03:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8712kb
  • [2023-11-06 09:03:01]
  • 提交

answer

#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
const int N = 1e5 + 5;
// const int B = 400;
// const int M = 2e5 + 5;
// const int base = 13331;
// const int mod = 998244353;
// const int mod = 1e9 + 7;
// const double pi = acos(-1);

int n, m, deg[N], ans[N], tot;
vector<int> num[N], adj[N];
void solve()
{
    cin >> n >> m;
    for (int i = 1, k, x; i <= n; i++)
    {
        cin >> k;
        while (k--)
        {
            cin >> x;
            num[x].push_back(i);
        }
    }
    for (int i = 1; i <= m; i++)
    {
        if (num[i].size() <= 1)
            continue;
        for (int j = 0; j < num[i].size() - 1; j++)
            adj[num[i][j]].push_back(num[i].back()), deg[num[i].back()]++;
    }
    priority_queue<int> que;
    for (int i = 1; i <= n; i++)
        if (!deg[i])
            que.push(i);
    while (!que.empty())
    {
        int cur = que.top();
        que.pop();
        ans[cur] = ++tot;
        for (int i : adj[cur])
            if (!--deg[i])
                que.push(i);
    }
    bool flag = false;
    for (int i = 1; i <= n; i++)
        if (ans[i] ^ i)
            flag = true;
    if (!flag)
        cout << "No\n";
    else
    {
        cout << "Yes\n";
        for (int i = 1; i <= n; i++)
            cout << ans[i] << ' ';
        cout << '\n';
    }
    for (int i = 1; i <= n; i++)
        adj[i].clear(), ans[i] = 0;
    for (int i = 1; i <= m; i++)
        num[i].clear();
    tot = 0;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    // cout << fixed << setprecision(10);
    while (t--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 8712kb

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
2 3 1 
No
No

result:

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