QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#293751#7738. Equivalent Rewritingucup-team859#WA 1ms3552kbC++171.9kb2023-12-29 18:08:152023-12-29 18:08:15

Judging History

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

  • [2023-12-29 18:08:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3552kb
  • [2023-12-29 18:08:15]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <iomanip>
#include <cmath>
#include <complex>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector <int> v(m, 0), grad(n, 0), ans;
    vector <vector <int>> op(n);
    vector <vector <int>> G(n);
    deque <int> dq;
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        op[i].resize(k);
        for (int j = 0; j < k; j++) {
            cin >> op[i][j];
            op[i][j]--;
            v[op[i][j]] = i;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (int) op[i].size(); j++) {
            if (v[op[i][j]] != i) {
                G[i].push_back(v[op[i][j]]);
                grad[v[op[i][j]]]++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (grad[i] == 0) {
            dq.push_back(i);
        }
    }
    bool ok = 0;
    while (!dq.empty()) {
        if (dq.front() != dq.back()) {
            ok = 1;
        }
        int curr = max(dq.front(), dq.back());
        if (dq.front() == curr) {
            dq.pop_front();
        }
        else {
            dq.pop_back();
        }
        ans.push_back(curr);
        for(int vecin : G[curr])
        {
            grad[vecin]--;
            if(grad[vecin] == 0)
                dq.push_back(vecin);
        }
    }
    if (ok) {
        cout << "YES\n";
        for (int i = 0; i < n; i++) {
            cout << ans[i] + 1 << ' ';
        }
        cout << '\n';
    }
    else {
        cout << "NO\n";
    }
}

int main() {
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int nrTeste;
    cin >> nrTeste;
    while (nrTeste--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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:

wrong answer Token parameter [name=yesno] equals to "YES", doesn't correspond to pattern "Yes|No" (test case 1)