Submission #529657

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
529657	2022-02-23T10:05:06 Z	topovik	Hiperkocka (COCI21_hiperkocka)	C++14	0 / 110	1000 ms	60996 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 = 4000;
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	35452 KB	Output is correct
2	Partially correct	18 ms	35428 KB	Output is partially correct
3	Partially correct	18 ms	35488 KB	Output is partially correct
4	Partially correct	24 ms	35532 KB	Output is partially correct
5	Partially correct	25 ms	35480 KB	Output is partially correct
6	Partially correct	68 ms	35532 KB	Output is partially correct
7	Partially correct	121 ms	35668 KB	Output is partially correct
8	Partially correct	147 ms	35808 KB	Output is partially correct
9	Partially correct	600 ms	60048 KB	Output is partially correct
10	Partially correct	247 ms	38220 KB	Output is partially correct
11	Partially correct	603 ms	41360 KB	Output is partially correct
12	Partially correct	636 ms	60132 KB	Output is partially correct
13	Partially correct	161 ms	36104 KB	Output is partially correct
14	Execution timed out	1088 ms	60996 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-