Submission #1222033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222033		totoro	Thousands Islands (IOI22_islands)	C++20	25.75 / 100	39 ms	10532 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;
    std::vector<int> seen(N, -1);  // when did we go out from this node
    auto dfs = [&](int node, auto dfs) -> int {
        if (seen[node] == -2) return -1;
        if (seen[node] != -1) {
            ans.push_back(ans[seen[node]] ^ 1);
            ans.push_back(ans[seen[node]]);
            return ans[seen[node]];
        }
        seen[node] = ans.size();
        for (int to : adj[node]) {
            if (to & 1) continue;
            ans.push_back(original_labels[to]);
            int toflip = dfs(V[to], dfs);
            if (toflip != -1) {
                ans.push_back(original_labels[to] ^ (original_labels[to] == toflip));
                return toflip;
            }
            ans.pop_back();
        }
        seen[node] = -2;
        return -1;
    };

    int toflip = dfs(0, dfs);
    if (toflip == -1) return false;
    return ans;
}

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