Submission #837552

#	Time	Username	Problem	Language	Result	Execution time	Memory
837552		tengiz05	Thousands Islands (IOI22_islands)	C++17	27.75 / 100	45 ms	4420 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>

using namespace std;

std::variant<bool, vector<int>> find_journey(int n, int m, vector<int> U, vector<int> V) {
    if (n == 2) {
        vector<int> e[n];
        for (int i = 0; i < m; i++) {
            e[U[i]].push_back(i);
        }
        if (e[0].size() >= 2 && e[1].size() >= 1) {
            return vector<int>{e[0][0], e[1][0], e[0][1], e[0][0], e[1][0], e[0][1]};
        } else {
            return false;
        }
    }
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        adj[U[i]].push_back(i);
    }
    if (adj[0].size() >= 2) {
        int a = adj[0][0];
        int b = adj[0][1];
        return vector<int>{a, a ^ 1, b, b ^ 1, a ^ 1, a, b ^ 1, b};
    }
    vector<int> path;
    vector<bool> vis(n);
    vector<int> ans;
    bool found = false;
    function<void(int)> dfs = [&](int u) {
        vis[u] = true;
        if (adj[u].size() >= 3) {
            found = true;
            adj[u].erase(find(adj[u].begin(), adj[u].end(), path.back() ^ 1));
            int a = adj[u][0];
            int b = adj[u][1];
            ans = path;
            vector<int> inter = {a, a ^ 1, b, b ^ 1, a ^ 1, a, b ^ 1, b};
            ans.insert(ans.end(), inter.begin(), inter.end());
            ans.insert(ans.end(), path.rbegin(), path.rend());
            return;
        }
        for (int i : adj[u]) {
            if (vis[V[i]]) {
                continue;
            }
            path.push_back(i);
            dfs(V[i]);
            if (found) return;
            path.pop_back();
        }
    };
    dfs(0);
    if (ans.empty()) {
        return false;
    } else {
        return ans;
    }
}

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