Submission #529658

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
529658	2022-02-23T10:05:36 Z	topovik	Hiperkocka (COCI21_hiperkocka)	C++14	14.9169 / 110	950 ms	63108 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 = 3000;
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 x1 = 0; x1 < M; x1++)
    {
        int x = rand() % (1 << n);
        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

14.916870122 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	35532 KB	Output is correct
2	Partially correct	18 ms	35532 KB	Output is partially correct
3	Partially correct	20 ms	35432 KB	Output is partially correct
4	Partially correct	22 ms	35548 KB	Output is partially correct
5	Partially correct	23 ms	35548 KB	Output is partially correct
6	Partially correct	62 ms	35540 KB	Output is partially correct
7	Partially correct	78 ms	35660 KB	Output is partially correct
8	Partially correct	113 ms	35788 KB	Output is partially correct
9	Partially correct	520 ms	58836 KB	Output is partially correct
10	Partially correct	188 ms	38248 KB	Output is partially correct
11	Partially correct	395 ms	41344 KB	Output is partially correct
12	Partially correct	485 ms	59144 KB	Output is partially correct
13	Partially correct	110 ms	36112 KB	Output is partially correct
14	Partially correct	879 ms	60076 KB	Output is partially correct
15	Partially correct	123 ms	45588 KB	Output is partially correct
16	Partially correct	441 ms	41420 KB	Output is partially correct
17	Partially correct	288 ms	56948 KB	Output is partially correct
18	Partially correct	516 ms	58956 KB	Output is partially correct
19	Partially correct	708 ms	63108 KB	Output is partially correct
20	Partially correct	637 ms	62428 KB	Output is partially correct
21	Partially correct	82 ms	35812 KB	Output is partially correct
22	Partially correct	429 ms	58188 KB	Output is partially correct
23	Partially correct	399 ms	57932 KB	Output is partially correct
24	Partially correct	883 ms	59820 KB	Output is partially correct
25	Partially correct	950 ms	60632 KB	Output is partially correct
26	Partially correct	359 ms	47456 KB	Output is partially correct