oj.uz

Submission #522843

# Submission time Handle Problem Language Result Execution time Memory
522843 2022-02-06T02:25:39 Z KoD Praktični (COCI18_prakticni) C++17
130 / 130
 157 ms 13252 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]) {
                const int x = C[e] ^ accum[u] ^ accum[v];
                if (x != 0) {
                    change.emplace_back(e, x);
                }
            }
        }
    })(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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5056 KB Output is correct
2 Correct 24 ms 5824 KB Output is correct
3 Correct 6 ms 1356 KB Output is correct
4 Correct 5 ms 1720 KB Output is correct
5 Correct 56 ms 12580 KB Output is correct
6 Correct 55 ms 11004 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2252 KB Output is correct
2 Correct 11 ms 2380 KB Output is correct
3 Correct 15 ms 3628 KB Output is correct
4 Correct 17 ms 4172 KB Output is correct
5 Correct 58 ms 9812 KB Output is correct
6 Correct 27 ms 6036 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6084 KB Output is correct
2 Correct 47 ms 8176 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 9608 KB Output is correct
2 Correct 115 ms 12080 KB Output is correct
3 Correct 2 ms 456 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7504 KB Output is correct
2 Correct 54 ms 8188 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8224 KB Output is correct
2 Correct 29 ms 5448 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9468 KB Output is correct
2 Correct 106 ms 9080 KB Output is correct
3 Correct 48 ms 8132 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 12432 KB Output is correct
2 Correct 157 ms 12276 KB Output is correct
3 Correct 124 ms 13252 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3164 KB Output is correct
2 Correct 23 ms 4244 KB Output is correct
3 Correct 70 ms 9900 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 10476 KB Output is correct
2 Correct 35 ms 6220 KB Output is correct
3 Correct 117 ms 12624 KB Output is correct