제출 #522842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522842		KoD	Praktični (COCI18_prakticni)	C++17	117 / 130	144 ms	14696 KiB

parkticni

#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, C[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';
    }
    for (const auto& [e, v] : change) {
        assert(v == 0);
    }
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 0 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13