Submission #529542

# Submission time Handle Problem Language Result Execution time Memory
529542 2022-02-23T06:29:03 Z Vimmer Hiperkocka (COCI21_hiperkocka) C++14
110 / 110
85 ms 32520 KB
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")

#define F first
#define S second
#define PB push_back
#define M ll(998244353)
#define sz(x) (ll)x.size()
#define N 1000005
#define pri(x) cout << x << endl
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

using namespace std;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;

vector <pair <int, int> > g[N];

vector <int> cube;

void dfs(int v, int x, int p)
{
    cube[v] = x;

    for (auto it : g[v])
    {
        if (it.F == p)
            continue;

        dfs(it.F, x ^ (1 << it.S), v);
    }
}

int main()
{
    istream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);
//    freopen("trains.in", "r", stdin);
//    freopen("trains.out", "w", stdout);

    int n;

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int x, y;

        cin >> x >> y;

        g[x].PB({y, i});

        g[y].PB({x, i});
    }

    cube.resize(n + 1);

    dfs(0, 0, -1);

    vector <vector <int> > ans; ans.clear();

    for (int i = 0; i < (1 << n); i++)
        if (__builtin_popcount(i) % 2 == 0)
        {
            ans.emplace_back();

            for (auto it : cube)
                ans.back().PB(it ^ i);
        }

    pri(sz(ans));

    for (auto it : ans)
    {
        for (auto itr : it)
            cout << itr << " ";

        cout << endl;
    }
}
# Verdict Execution time Memory Grader output
1 Correct 12 ms 23748 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23776 KB Output is correct
4 Correct 16 ms 23796 KB Output is correct
5 Correct 13 ms 23756 KB Output is correct
6 Correct 13 ms 23796 KB Output is correct
7 Correct 16 ms 23760 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 66 ms 32408 KB Output is correct
10 Correct 19 ms 24568 KB Output is correct
11 Correct 23 ms 25208 KB Output is correct
12 Correct 62 ms 32460 KB Output is correct
13 Correct 13 ms 23884 KB Output is correct
14 Correct 63 ms 32380 KB Output is correct
15 Correct 36 ms 26900 KB Output is correct
16 Correct 28 ms 25204 KB Output is correct
17 Correct 63 ms 32380 KB Output is correct
18 Correct 85 ms 32520 KB Output is correct
19 Correct 63 ms 32396 KB Output is correct
20 Correct 64 ms 32380 KB Output is correct
21 Correct 13 ms 23756 KB Output is correct
22 Correct 81 ms 32448 KB Output is correct
23 Correct 62 ms 32380 KB Output is correct
24 Correct 64 ms 32468 KB Output is correct
25 Correct 63 ms 32420 KB Output is correct
26 Correct 35 ms 26888 KB Output is correct