Submission #1064001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064001		vjudge1	Thousands Islands (IOI22_islands)	C++17	0 / 100	242 ms	416440 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
    int nr = 2 * m * (1 << m);
    vector<vector<ii> > L(n);
    for(int i = 0; i < m; ++i) {
        int u = U[i], v = V[i];
        L[u].push_back({v, 2 * i});
        L[v].push_back({u, 2 * i + 1});
    }
    auto get_vec = [&](int bm, int ultm, int u) -> vi {
        vi Re;
        for(auto [it, id] : L[u]) {
            if(id / 2 != ultm && ((id & 1) == !!(bm & (1 << (id / 2))))) {
                int b2 = bm ^ (1 << (id / 2));
                Re.push_back(b2 * 2 * m + id);
            }
        }
        return Re;
    };
    bool ok = false;
    vi viz(nr, 0);
    function<void(int)> dfs = [&](int id) {
        int bm = id / (2 * m);
        int ultm = id % (2 * m) / 2;
        int u; 
        if(id & 1) u = U[ultm];
        else u = V[ultm];


        if(u == 0 && !bm) {
            ok = 1;
            //printf("!!!! Am vizitat nodul %d cu muchia %d (%d -> %d), bm=%d\n", u, ultm, U[ultm], V[ultm], bm);
            return;
        }

        if(viz[id]) return;
        viz[id] = 1;

//        printf("Am vizitat nodul %d cu muchia %d (%d -> %d), bm=%d\n", u, ultm, U[ultm], V[ultm], bm);

        auto Vec = get_vec(bm, ultm, u);
        for(auto it : Vec) {
            dfs(it);
        }
    };
    for(auto [it, id]: L[0]) {
        int bm = (1 << (id / 2));
        dfs(bm * 2 * m + id);
    }
    return ok;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45