Submission #529655

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
529655	2022-02-23T10:03:13 Z	topovik	Hiperkocka (COCI21_hiperkocka)	C++14	4.29083 / 110	938 ms	47816 KB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef long double ld;

const ll oo = 1e18 + 7;

const int N = 5e5 + 10;
const int M = 5000;
const int M1 = 1e6;

int n;
map <int, bool> mrk[N];
vector <int> a[N];
vector <int> ans;
vector <vector <int> > ans1;
vector <pair<int, int> > vc;
bool g = 1;

bool check(int x)
{
    for (int i = 0; i < n; i++)
        if (x == (1 << i)) return 1;
    return 0;
}

void Rec(int x, int y, int prv)
{
    ans1.back()[y] = x;
    for (auto i : a[y])
        if (i != prv)
    {
        int j;
        for (j = 0; j < (1 << n); (j == 0 ? j++ : j <<= 1))
            if (!mrk[min(x, j ^ x)][max(j ^ x, x)] && (j ^ x) != x)
        {
            mrk[min(x, j ^ x)][max(j ^ x, x)] = 1;
            vc.pb({min(x, j ^ x), max(j ^ x, x)});
            Rec(j ^ x, i, y);
            break;
        }
        g &= (j != (1 << n));
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        a[x].pb(y);
        a[y].pb(x);
    }
    while (1)
    {
        bool g1 = 0;
        for (int i = 0; i <= n; i++)
        {
            ans1.pb({});
            ans1.back().resize(n + 1);
            vc.clear();
            g = 1;
            Rec(i, 0, 0);
            if (g)
            {
                g1 = 1;
                break;
            }
            ans1.pop_back();
            for (auto j : vc) mrk[j.f][j.s] = 0;
        }
        if (!g1) break;
    }

    int k = ans1.size();
    for (int x = 0; x < min((1 << n), M); x++)
    {
        for (int ps = 0; ps < k; ps++)
        {
            bool g = 1;
            for (int i = 0; i <= n; i++)
                for (auto j : a[i]) g &= !mrk[min(ans1[ps][i] ^ x, ans1[ps][j] ^ x)][max(ans1[ps][i] ^ x, ans1[ps][j] ^ x)];
            if (g)
            {
                ans1.pb(ans1[ps]);
                for (int i = 0; i <= n; i++) ans1.back()[i] ^= x;
                for (int i = 0; i <= n; i++)
                    for (auto j : a[i]) mrk[min(ans1.back()[i], ans1.back()[j])][max(ans1.back()[i], ans1.back()[j])] = 1;
            }
        }
    }
    cout << ans1.size() << endl;
    for (auto i : ans1)
    {
        for (auto j : i) cout << j << " ";
        cout << endl;
    }
}
/*
5 3
2 1 1 2 2 3
2 3 3 4 4 5
4 1 1 2 2 3 3 4 4 5
*/

Subtask #1

4.290832524 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	35532 KB	Output is correct
2	Partially correct	21 ms	35532 KB	Output is partially correct
3	Partially correct	18 ms	35480 KB	Output is partially correct
4	Partially correct	28 ms	35532 KB	Output is partially correct
5	Partially correct	28 ms	35492 KB	Output is partially correct
6	Partially correct	21 ms	35576 KB	Output is partially correct
7	Partially correct	28 ms	35612 KB	Output is partially correct
8	Partially correct	47 ms	35748 KB	Output is partially correct
9	Partially correct	428 ms	41208 KB	Output is partially correct
10	Partially correct	258 ms	37832 KB	Output is partially correct
11	Partially correct	611 ms	39532 KB	Output is partially correct
12	Partially correct	362 ms	40664 KB	Output is partially correct
13	Partially correct	81 ms	36084 KB	Output is partially correct
14	Partially correct	756 ms	42944 KB	Output is partially correct
15	Partially correct	75 ms	37668 KB	Output is partially correct
16	Partially correct	551 ms	39484 KB	Output is partially correct
17	Partially correct	201 ms	40972 KB	Output is partially correct
18	Partially correct	488 ms	40596 KB	Output is partially correct
19	Partially correct	524 ms	47816 KB	Output is partially correct
20	Partially correct	395 ms	46704 KB	Output is partially correct
21	Partially correct	43 ms	35908 KB	Output is partially correct
22	Partially correct	291 ms	39944 KB	Output is partially correct
23	Partially correct	295 ms	41040 KB	Output is partially correct
24	Partially correct	795 ms	42780 KB	Output is partially correct
25	Partially correct	938 ms	43836 KB	Output is partially correct
26	Partially correct	354 ms	39884 KB	Output is partially correct