QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#685962#7738. Equivalent RewritingwangcqWA 0ms3788kbC++233.1kb2024-10-28 22:15:502024-10-28 22:15:51

Judging History

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

  • [2024-10-28 22:15:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3788kb
  • [2024-10-28 22:15:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-10;
const int N = 100010;
const double PII = acos(-1);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f;
// int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// int dir[8][2] = {{1, 0}, {1, -1}, {1, 1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
// std::mt19937 rng {std::chrono::steady_clock::now().time_since_epoch().count()};

template <typename T>
void debug(T x) {
    cerr << x << '\n';
}

template <typename T, typename... Args>
void debug(T x, Args... args) {
    cerr << x << ' ';
    debug(args...);
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m + 1);
    vector<vector<int>> g(n + 1);
    map<int, int> mp;
    vector<int> in(n + 1);
    for (int i = 1; i <= n; i ++ ) {
        int cnt; cin >> cnt;
        vector<int> tmp(cnt + 1);
        for (int j = 1; j <= cnt; j ++ ) {
            int x;
            cin >> x;
            tmp[j] = x;
            a[x] = i;
        }
        bool ok = 0;
        for (int j = 1; j <= cnt; j ++ ) {
            if (mp[tmp[j]]) {
                // g[i - 1].push_back(i);
                ok = 1;
            }
        }
        if (ok) {
            g[i - 1].push_back(i);
            in[i] ++;
        }
        mp.clear();
        for (int j = 1; j <= cnt; j ++ ) {
            mp[tmp[j]] = 1;
        }
    }

    unordered_map<int, int> ump;
    int cnt = 0;
    for (int i = 1; i <= m; i ++ ) {
        // cout << a[i] << " \n"[i == m];
        if (ump[a[i]] == 0) cnt ++;
        ump[a[i]] = 1;
    }
    vector<int> ans;
    if (cnt < n) {
        for (int i = 1; i <= n; i ++ ) {
            if (ump[i] == 0) {
                ans.push_back(i);
            } 
        }
        for (int i = 1; i <= n; i ++ ) {
            if (ump[i]) {
                ans.push_back(i);
            }
        }
        cout << "Yes" << '\n';
        for (int i = 0; i < (int)ans.size(); i ++ ) {
            cout << ans[i] << " \n"[i == (int)ans.size() - 1];
        }
    } else {
        queue<int> q;
        for (int i = 2; i <= n; i ++ ) {
            if (in[i] == 0) {
                q.push(i);
            }
        }
        q.push(1);
        if (q.size() >= 2) {
            while (q.size()) {
                auto t = q.front();
                ans.push_back(t);
                q.pop();
                for (auto v : g[t]) {
                    in[v] --;
                    if (in[v] == 0) {
                        q.push(v);
                    }
                }
            }
            cout << "Yes" << '\n';
            for (int i = 0; i < (int)ans.size(); i ++ ) {
                cout << ans[i] << " \n"[i == (int)ans.size() - 1];
            }
        } else {
            cout << "No" << '\n';
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T -- ) {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3788kb

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:

ok OK. (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3788kb

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:

Yes
1 2 3 4 5 6 7 8 9 10

result:

wrong answer two transactions are same. (test case 1)