답안 #528469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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	-