Submission #528469

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
528469	2022-02-20T10:47:49 Z	Slavita	Hiperkocka (COCI21_hiperkocka)	C++14	0 / 110	81 ms	35876 KB

Main

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define el "\n"
#define F first
#define S second
using namespace std;

const int N = (1 << 16) + 5;
int st[N];

set <pair <int, int> > G[N];
vector <int> g[N];
vector <int> cur;
set <int> level[N];
int n, a[N], b[N], root;
vector <vector <int> > ans;

bool go(int a, int b, int pr) {
    cur[b] = a;
//    cerr << sz(G[a]) << " " << sz(g[b]) - (b != root) << el;
    if (sz(G[a]) < sz(g[b]) - (b != root)) {
        return 0;
    }
    int it = 0;
    bool can = 1;
    for (auto x : G[a]) {
        if (it < sz(g[b]) && g[b][it] == pr) {
            it++;
        }
        if (it == sz(g[b])) {
            break;
        }
        can &= go(x.S, g[b][it], b);
        it++;
    }
    return can;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        g[a[i]].pb(b[i]);
        g[b[i]].pb(a[i]);
    }
    cur.resize(n + 1);
    for (int i = 0; i <= n; i++) {
        if (sz(g[i]) == 1) {
            root = i;
        }
    }
    for (int i = 0; i <= n; i++) {
        sort(all(g[i]), [&](int a, int b) {return (sz(g[a]) > sz(g[b]));});
    }

    for (int i = 0; i < (1 << n); i++) {
        level[__builtin_popcount(i)].insert(i);
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                continue;
            }
            st[i]++;
        }
    }
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                continue;
            }
            G[i].insert({n - st[i + (1 << j)], (i + (1 << j))});
        }
    }
    for (int lvl = 0; lvl <= n; lvl++) {
        for (auto x : level[lvl]) {
            while (go(x, root, -1)) {
                ans.pb(cur);
                for (int i = 0; i <= n; i++) {
                    int cnt = sz(g[i]) - (i != root);
                    st[cur[i]] -= cnt;
//                    cerr << sz(G[cur[i]]) << el;
                    while (cnt--) {
                        G[cur[i]].erase(G[cur[i]].begin());
                    }
//                    cerr << sz(G[cur[i]]) << el;
                    if (!st[cur[i]] && __builtin_popcount(cur[i]) > lvl) {
                        level[__builtin_popcount(cur[i])].erase(cur[i]);
                    }
                }
            }
        }
    }
    cout << sz(ans) << el;
    for (int i = 0; i < sz(ans); i++) {
        for (auto x : ans[i]) {
            cout << x << " ";
        }
        cout << el;
    }
}

Subtask #1

0.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	8012 KB	Output is correct
2	Partially correct	5 ms	8012 KB	Output is partially correct
3	Partially correct	5 ms	8140 KB	Output is partially correct
4	Partially correct	6 ms	8016 KB	Output is partially correct
5	Partially correct	5 ms	8016 KB	Output is partially correct
6	Partially correct	4 ms	8012 KB	Output is partially correct
7	Partially correct	4 ms	8140 KB	Output is partially correct
8	Partially correct	5 ms	8268 KB	Output is partially correct
9	Partially correct	81 ms	35876 KB	Output is partially correct
10	Partially correct	11 ms	10828 KB	Output is partially correct
11	Incorrect	23 ms	14324 KB	Duplicate edges
12	Halted	0 ms	0 KB	-