oj.uz

Submission #522841

# Submission time Handle Problem Language Result Execution time Memory
522841 2022-02-06T02:20:38 Z KoD Praktični (COCI18_prakticni) C++17
0 / 130
 127 ms 14848 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    vector<int> C(M);
    vector<vector<pair<int, int>>> graph(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        std::cin >> a >> b >> C[i];
        a -= 1, b -= 1;
        graph[a].emplace_back(b, i);
        graph[b].emplace_back(a, i);
    }
    vector<int> accum(N), depth(N, -1);
    depth[0] = 0;
    vector<pair<int, int>> change;
    RecLambda([&](auto&& dfs, const int u, const int p) -> void {
        for (const auto& [v, e] : graph[u]) {
            if (v == p) continue;
            if (depth[v] == -1) {
                accum[v] = accum[u] ^ C[e];
                depth[v] = depth[u] + 1;
                dfs(v, u);
            } else if (depth[u] > depth[v] and accum[u] != accum[v]) {
                change.emplace_back(e, accum[u] ^ accum[v]);
            }
        }
    })(0, 0);
    vector<int> base;
    for (const auto& [e, v] : change) {
        int x = v;
        for (const int b : base) {
            if (x > (x ^ b)) {
                x ^= b;
            }
        }
        if (x != 0) {
            base.push_back(x);
        }
    }
    std::cout << base.size() << '\n';
    for (const int b : base) {
        vector<int> apply;
        for (auto& [e, v] : change) {
            if (v > (v ^ b)) {
                v ^= b;
                apply.push_back(e);
            }
        }
        std::cout << b << ' ' << apply.size();
        std::sort(apply.begin(), apply.end());
        for (const int e : apply) {
            std::cout << ' ' << e + 1;
        }
        std::cout << '\n';
    }
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 7848 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 3520 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 6980 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 11944 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 9204 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 10720 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 11588 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 14848 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3896 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 12744 KB There is a simple cycle which is not good
2 Halted 0 ms 0 KB -