oj.uz

답안 #522842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522842 2022-02-06T02:23:57 Z KoD Praktični (COCI18_prakticni) C++17
117 / 130
 144 ms 14696 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, 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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 4932 KB Output is correct
2 Correct 26 ms 6596 KB Output is correct
3 Correct 6 ms 1484 KB Output is correct
4 Correct 6 ms 1996 KB Output is correct
5 Correct 55 ms 13860 KB Output is correct
6 Correct 66 ms 12500 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 2252 KB Output is correct
2 Correct 11 ms 2992 KB Output is correct
3 Correct 15 ms 4172 KB Output is correct
4 Correct 17 ms 4796 KB Output is correct
5 Correct 48 ms 11076 KB Output is correct
6 Correct 29 ms 6980 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 5824 KB Output is correct
2 Correct 48 ms 9156 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 9284 KB Output is correct
2 Incorrect 122 ms 13192 KB There is a simple cycle which is not good
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 7212 KB Output is correct
2 Correct 56 ms 9348 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 7876 KB Output is correct
2 Correct 32 ms 6212 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 9156 KB Output is correct
2 Correct 101 ms 10132 KB Output is correct
3 Correct 51 ms 9348 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 11960 KB Output is correct
2 Correct 144 ms 13748 KB Output is correct
3 Correct 121 ms 14696 KB Output is correct

Subtask #9
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3148 KB Output is correct
2 Correct 32 ms 4836 KB Output is correct
3 Correct 70 ms 11148 KB Output is correct

Subtask #10
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 10028 KB Output is correct
2 Correct 74 ms 7248 KB Output is correct
3 Correct 102 ms 14076 KB Output is correct