Submission #496185

# Submission time Handle Problem Language Result Execution time Memory
496185 2021-12-21T01:00:58 Z model_code Hiperkocka (COCI21_hiperkocka) C++17
110 / 110
58 ms 8816 KB
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define _ << " _ " <<

template<class> struct is_container : false_type {};
template<class... Ts> struct is_container<vector<Ts...>> : true_type {};
template<class... Ts> struct is_container<map<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_map<Ts...>> : true_type {};
template<class... Ts> struct is_container<set<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_set<Ts...>> : true_type {};
template<class... Ts> struct is_container<multiset<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_multiset<Ts...>> : true_type {};
template<class T, class = typename enable_if<is_container<T>::value>::type>
ostream& operator<<(ostream &o, T x) {
  int f = 1;
  o << "{";
  for (auto y : x) {
    o << (f ? "" : ", ") << y;
    f = 0;
  }
  return o << "}";
}
template<class T, class U>
ostream& operator<<(ostream &o, pair<T, U> x) {
  return o << "(" << x.first << ", " << x.second << ")";
}

#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

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

    int n;
    cin >> n;

    vector<vi> e(n + 1);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }


    vi ord(n + 1, -1), p(n + 1);
    int t = 0;
    queue<int> Q({0});
    ord[0] = t++;
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (int y : e[x]) {
            if (ord[y] != -1) continue;
            ord[y] = t++;
            p[ord[y]] = ord[x];
            Q.push(y);
        }
    }

    
    vector<vi> sol = {{0, 1}};
    for (int i = 1; i < n; i++) {
        int k = sol.size();
        for (int j = 0; j < k; j++) {
            sol.push_back(sol[j]);
            for (auto& x : sol.back())
                x ^= 1 ^ (1 << i);
        }

        for (auto& v : sol)
            v.push_back(v[p[i + 1]] ^ (1 << i));
    }


    cout << sol.size() << '\n';
    for (auto& v : sol) {
        for (int i = 0; i <= n; i++)
            cout << v[ord[i]] << ' ';
        cout << '\n';
    }

    return 0;
}

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 53 ms 8636 KB Output is correct
10 Correct 6 ms 1100 KB Output is correct
11 Correct 12 ms 2136 KB Output is correct
12 Correct 50 ms 8648 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 52 ms 8712 KB Output is correct
15 Correct 26 ms 4104 KB Output is correct
16 Correct 12 ms 2148 KB Output is correct
17 Correct 54 ms 8636 KB Output is correct
18 Correct 50 ms 8724 KB Output is correct
19 Correct 58 ms 8816 KB Output is correct
20 Correct 50 ms 8700 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 54 ms 8644 KB Output is correct
23 Correct 58 ms 8696 KB Output is correct
24 Correct 51 ms 8636 KB Output is correct
25 Correct 49 ms 8700 KB Output is correct
26 Correct 23 ms 4120 KB Output is correct