Submission #1222031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222031		totoro	Thousands Islands (IOI22_islands)	C++20	22.75 / 100	1094 ms	1907268 KiB

islands

#include "islands.h"

#include <iostream>
#include <map>
#include <variant>
#include <vector>

std::variant<bool, std::vector<int>> find_journey_connected(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> original_labels);

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
    std::vector<std::vector<int>> canoesfrom(N);
    for (int i = 0; i < M; ++i) canoesfrom[U[i]].push_back(i);
    std::vector<bool> seen(N);

    std::vector<int> stack = {0};
    while (!stack.empty()) {
        int node = stack.back();
        stack.pop_back();
        if (seen[node]) continue;
        seen[node] = true;
        for (int i : canoesfrom[node]) {
            stack.push_back(V[i]);
        }
    }

    std::vector<int> newu, newv, original_labels;
    int newm = 0;
    for (int i = 0; i < N; ++i) {
        if (!seen[i]) continue;
        for (int out : canoesfrom[i]) {
            newu.push_back(U[out]);
            newv.push_back(V[out]);
            original_labels.push_back(out);
            ++newm;
        }
    }
    return find_journey_connected(N, newm, newu, newv, original_labels);
}

// everything except line case works
std::variant<bool, std::vector<int>> find_journey_connected(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> original_labels) {
    std::vector<std::vector<int>> adj(N);
    for (int i = 0; i < M; ++i) {
        adj[U[i]].push_back(i);
    }

    std::vector<int> ans;
    auto dfs = [&](int node, int waka, auto dfs) -> bool {
        std::vector<int> goodadj;
        for (int to : adj[node]) {
            if (waka != -1 && (original_labels[to] & (-2)) == (original_labels[waka] & (-2))) continue;  // don't go back
            goodadj.push_back(to);
        }
        if (goodadj.size() >= 2) {
            ans.push_back(original_labels[goodadj[0]]);
            ans.push_back(original_labels[goodadj[0]] ^ 1);
            ans.push_back(original_labels[goodadj[1]]);
            ans.push_back(original_labels[goodadj[1]] ^ 1);
            ans.push_back(original_labels[goodadj[0]] ^ 1);
            ans.push_back(original_labels[goodadj[0]]);
            ans.push_back(original_labels[goodadj[1]] ^ 1);
            ans.push_back(original_labels[goodadj[1]]);
            return true;
        }
        for (int to : goodadj) {
            ans.push_back(original_labels[to]);
            if (dfs(V[to], to, dfs)) {
                ans.push_back(original_labels[to]);
                return true;
            }
            ans.pop_back();
        }
        return false;
    };

    bool exists = dfs(0, -1, dfs);
    if (!exists) return false;
    return ans;
}

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