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

Main

#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;
}

Subtask #1

110.0 / 110.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