Submission #529666

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

0.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	35532 KB	Output is correct
2	Partially correct	18 ms	35504 KB	Output is partially correct
3	Partially correct	20 ms	35440 KB	Output is partially correct
4	Partially correct	25 ms	35556 KB	Output is partially correct
5	Partially correct	24 ms	35568 KB	Output is partially correct
6	Partially correct	58 ms	35532 KB	Output is partially correct
7	Partially correct	87 ms	35660 KB	Output is partially correct
8	Partially correct	122 ms	35788 KB	Output is partially correct
9	Partially correct	454 ms	58964 KB	Output is partially correct
10	Partially correct	222 ms	38192 KB	Output is partially correct
11	Partially correct	421 ms	41392 KB	Output is partially correct
12	Partially correct	445 ms	58924 KB	Output is partially correct
13	Partially correct	113 ms	36112 KB	Output is partially correct
14	Partially correct	846 ms	60004 KB	Output is partially correct
15	Partially correct	114 ms	45696 KB	Output is partially correct
16	Partially correct	356 ms	41400 KB	Output is partially correct
17	Partially correct	310 ms	56888 KB	Output is partially correct
18	Partially correct	606 ms	58936 KB	Output is partially correct
19	Partially correct	738 ms	63060 KB	Output is partially correct
20	Partially correct	756 ms	62468 KB	Output is partially correct
21	Partially correct	87 ms	35808 KB	Output is partially correct
22	Partially correct	363 ms	58136 KB	Output is partially correct
23	Partially correct	437 ms	57940 KB	Output is partially correct
24	Partially correct	813 ms	59664 KB	Output is partially correct
25	Execution timed out	1024 ms	60680 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-