Submission #529656

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
529656	2022-02-23T10:04:30 Z	topovik	Hiperkocka (COCI21_hiperkocka)	C++14	0 / 110	1000 ms	60936 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 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

0.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	35532 KB	Output is correct
2	Partially correct	19 ms	35532 KB	Output is partially correct
3	Partially correct	18 ms	35532 KB	Output is partially correct
4	Partially correct	25 ms	35552 KB	Output is partially correct
5	Partially correct	26 ms	35568 KB	Output is partially correct
6	Partially correct	82 ms	35584 KB	Output is partially correct
7	Partially correct	116 ms	35660 KB	Output is partially correct
8	Partially correct	167 ms	35788 KB	Output is partially correct
9	Partially correct	727 ms	60936 KB	Output is partially correct
10	Partially correct	312 ms	38176 KB	Output is partially correct
11	Partially correct	581 ms	41564 KB	Output is partially correct
12	Partially correct	693 ms	60840 KB	Output is partially correct
13	Partially correct	172 ms	36044 KB	Output is partially correct
14	Execution timed out	1083 ms	60300 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-