QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#418869#7738. Equivalent Rewritingshift#WA 1ms3900kbC++205.6kb2024-05-23 16:14:472024-05-23 16:14:48

Judging History

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

  • [2024-05-23 16:14:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3900kb
  • [2024-05-23 16:14:47]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

struct DSU {
    std::vector<int> f;
    DSU(int n): f(n) { std::iota(f.begin(), f.end(), 0); }
    int find(int x){
        if(x != f[x]) f[x] = find(f[x]);
        return f[x];
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        f[u] = v;
    }

};

constexpr int Base = 1145141, P = 1e9 + 7;

i64 hash(const std::vector<int> &vec) {
    i64 h = 0;
    for(int i = 0; i < vec.size(); i ++ ) {
        h = h * Base % P + vec[i];
        h %= P;
    }
    return h;
}

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::map<i64, std::vector<int>> mp;
    std::vector<std::vector<int>> p(m + 1);
    for(int i = 1; i <= n; i ++ ) {
        int k, x;
        std::cin >> k;
        std::vector<int> vec;
        while(k -- ) {
            std::cin >> x;
            vec.push_back(x);
            p[x].push_back(i);
        }
        mp[hash(vec)].push_back(i);
    }

    std::vector<int> seq(n + 1);
    std::iota(seq.begin(), seq.end(), 0);
    for(auto [x, y] : mp) {
        if(y.size() > 1) {
            std::swap(seq[y[0]], seq[y[1]]);
            std::cout << "Yes" << '\n';
            for(int i = 1; i <= n; i ++ ) {
                std::cout << seq[i] << " \n"[i == n];
            }
            return;
        }
    }

    std::set<std::pair<int, int>> S;
    DSU dsu(n + 1);
    std::vector<int> in(n + 1), out(n + 1);
    std::vector<std::vector<int>> adj(n + 1), radj(n + 1);
    for(int i = 1; i <= m; i ++ ) {
        int lst = -1;
        for(auto x : p[i]) {
            if(lst != -1) {
                if(!S.count({lst, x})) {
                    dsu.merge(lst, x);
                    adj[lst].push_back(x);
                    in[x] ++;
                    S.insert({lst, x});
                }
                if(!S.count({x, lst})) {
                    radj[x].push_back(lst);
                    out[lst] ++;
                    S.insert({x, lst});
                }
            }
            lst = x;
        }
    }

    auto get = [&](std::vector<std::vector<int>> &adj, int s) -> std::vector<int> {
        std::vector<int> vec;
        std::queue<int> q;
        q.push(s);
        while(!q.empty()) {
            auto u = q.front(); q.pop();
            vec.push_back(u);
            for(auto v : adj[u]) {
                -- out[v];
                if(!out[v]) q.push(v);
            }
        }
        std::reverse(vec.begin(), vec.end());
        return vec;
    };

    

    for(int i = 1; i <= n; i ++ ) {
        if(in[i] > 1) {
            auto a = get(radj, radj[i][0]);
            auto b = get(radj, radj[i][1]);
            if(a[0] < b[0]) std::swap(a, b);

            std::vector<int> idx;
            for(auto x : a) {
                idx.push_back(x);
            }
            for(auto x : b) {
                idx.push_back(x);
            }
            std::sort(idx.begin(), idx.end());
            int cur = 0;
            for(int i = 0; i < a.size(); i ++ ) {
                seq[idx[cur]] = a[i];
                cur ++;
            }
            for(int i = 0; i < b.size(); i ++ ) {
                seq[idx[cur]] = b[i];
                cur ++;
            }

            std::cout << "Yes" << '\n';
            for(int i = 1; i <= n; i ++ ) {
                std::cout << seq[i] << " \n"[i == n];
            }
            return ;
        }
    }

    for(int i = n; i >= 1; i -- ) {
        if(out[i] > 1) {
            auto a = get(adj, adj[i][0]);
            auto b = get(adj, adj[i][1]);
            if(a[0] < b[0]) std::swap(a, b);
            std::vector<int> idx;
            for(auto x : a) {
                idx.push_back(x);
            }
            for(auto x : b) {
                idx.push_back(x);
            }
            std::sort(idx.begin(), idx.end());
            int cur = 0;
            for(int i = 0; i < a.size(); i ++ ) {
                seq[idx[cur]] = a[i];
                cur ++;
            }
            for(int i = 0; i < b.size(); i ++ ) {
                seq[idx[cur]] = b[i];
                cur ++;
            }

            std::cout << "Yes" << '\n';
            for(int i = 1; i <= n; i ++ ) {
                std::cout << seq[i] << " \n"[i == n];
            }
            return ;
        }
    }

    std::set<int> R;
    std::vector<std::vector<int>> q(n + 1);
    for(int i = 1; i <= n; i ++ ) {
        R.insert(dsu.find(i));
        q[dsu.find(i)].push_back(i);
    }

    if(R.size() > 1) {
        int p1 = -1, p2 = -1;
        for(int i = 1; i <= n; i ++ ) {
            if(q[i].size()) {
                if(p1 == -1) {
                    p1 = i;
                } else {
                    p2 = i;
                    break;
                }
            }
        }
        if(q[p1][0] < q[p2][0]) std::swap(q[p1], q[p2]);
        std::cout << "Yes" << '\n';
        std::vector<int> ans;
        for(int i = 1; i <= n; i ++ ) {
            if(q[i].size()) {
                for(auto x : q[i]) {
                    ans.push_back(x);
                }
            }
        }
        assert(ans.size() == n);
        for(int i = 0; i < n; i ++ ) {
            std::cout << ans[i] << " \n"[i == n - 1];
        }
        return;
    }

    std::cout << "No" << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    std::cin >> T;

    while(T -- ) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3604kb

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: 0
Accepted
time: 0ms
memory: 3636kb

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
3 1 2 4 5 6 7 8 9 10

result:

ok OK. (1 test case)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

1
20 5
5 4 1 2 5 3
2 5 3
3 5 1 2
5 4 5 1 3 2
3 4 2 5
5 3 1 5 4 2
5 5 1 2 3 4
1 3
4 5 1 2 3
4 4 1 3 5
2 5 2
4 2 3 5 1
3 2 4 5
5 2 3 4 1 5
4 5 2 4 3
1 2
2 4 3
4 4 5 3 1
5 4 1 5 3 2
3 5 1 3

output:

Yes
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

result:

ok OK. (1 test case)

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3896kb

input:

1
40 10
2 4 1
10 5 8 2 3 6 7 4 1 10 9
3 10 9 7
1 9
10 10 5 6 9 2 8 3 1 4 7
7 8 4 7 5 2 3 6
5 2 6 5 1 10
6 6 5 4 8 7 1
3 4 9 8
9 9 10 4 2 1 8 7 5 3
2 5 7
9 8 6 1 2 9 7 5 10 3
2 8 1
8 8 3 10 9 1 4 5 6
2 3 4
5 5 3 6 2 7
10 3 2 8 9 10 1 7 4 6 5
2 1 9
1 1
3 3 7 4
5 2 6 5 7 1
7 3 2 4 9 10 6 1
1 4
5 6 4 5 ...

output:

Yes
39 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 1 40

result:

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