Submission #509769

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
509769	2022-01-14T09:36:57 Z	KoD	Hiperkocka (COCI21_hiperkocka)	C++17	110 / 110	165 ms	43592 KB

Main

#include <bits/stdc++.h>

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

vector<std::map<int, int>> build(vector<pair<int, int>> edge) {
    const int n = edge.size();
    if (n == 1) {
        std::map<int, int> ret;
        const auto& [x, y] = edge[0];
        ret[x] = 0;
        ret[y] = 1;
        return {ret};
    }
    std::map<int, int> deg;
    for (const auto& [x, y] : edge) {
        deg[x] += 1;
        deg[y] += 1;
    }
    for (int i = 0; i < n; ++i) {
        auto& [x, y] = edge[i];
        if (deg[y] == 1) std::swap(x, y);
        if (deg[x] == 1) {
            std::swap(edge[i], edge[n - 1]);
            break;
        }
    }
    const auto [cut, other] = edge[n - 1];
    edge.pop_back();
    vector<std::map<int, int>> ret;
    auto smaller = build(edge);
    for (const auto& v : smaller) {
        {
            auto& add = ret.emplace_back(v);
            for (auto& [x, y] : add) {
                y <<= 1;
            }
            add[cut] = add[other] ^ 1;
        }
        {
            auto& add = ret.emplace_back(v);
            for (auto& [x, y] : add) {
                y = ((y ^ 1) << 1) ^ 1;
            }
            add[cut] = add[other] ^ 1;
        }
    }
    return ret;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<pair<int, int>> edge(N);
    for (auto& [x, y] : edge) {
        std::cin >> x >> y;
    }
    auto ans = build(edge);
    std::cout << (1 << (N - 1)) << '\n';
    for (auto& v : ans) {
        for (int i = 0; i <= N; ++i) {
            std::cout << v[i] << " \n"[i == N];
        }
    }
    return 0;
}

Subtask #1

110.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	312 KB	Output is correct
4	Correct	0 ms	312 KB	Output is correct
5	Correct	0 ms	312 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	2 ms	716 KB	Output is correct
9	Correct	127 ms	43556 KB	Output is correct
10	Correct	12 ms	4812 KB	Output is correct
11	Correct	27 ms	9804 KB	Output is correct
12	Correct	116 ms	43548 KB	Output is correct
13	Correct	3 ms	1204 KB	Output is correct
14	Correct	113 ms	43480 KB	Output is correct
15	Correct	56 ms	20636 KB	Output is correct
16	Correct	25 ms	9800 KB	Output is correct
17	Correct	115 ms	43560 KB	Output is correct
18	Correct	165 ms	43592 KB	Output is correct
19	Correct	119 ms	43528 KB	Output is correct
20	Correct	120 ms	43560 KB	Output is correct
21	Correct	2 ms	728 KB	Output is correct
22	Correct	121 ms	43588 KB	Output is correct
23	Correct	118 ms	43564 KB	Output is correct
24	Correct	119 ms	43504 KB	Output is correct
25	Correct	122 ms	43492 KB	Output is correct
26	Correct	71 ms	20620 KB	Output is correct