Submission #709495

#	Time	Username	Problem	Language	Result	Execution time	Memory
709495		finn__	Thousands Islands (IOI22_islands)	C++17	0 / 100	4 ms	5588 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    size_t u, v, i;

    Edge(size_t u_, size_t v_, size_t i_) { u = u_, v = v_, i = i_; }
};

constexpr size_t N = 100000;

vector<Edge> g[N], t[N];
bool visited[N];
size_t preorder[N], postorder[N];
vector<Edge> special_edges;

bool find_tree_path(size_t u, size_t z, vector<int> &path, size_t p = SIZE_MAX)
{
    if (u == z)
        return 1;
    for (auto const &[_, v, i] : t[u])
        if (v != p)
        {
            path.push_back(i);
            if (v == z || find_tree_path(v, z, path, u))
                return 1;
            path.pop_back();
        }
    return 0;
}

pair<size_t, size_t> find_dfs_tree(size_t u, size_t i1 = 0, size_t i2 = 0)
{
    visited[u] = 1;
    preorder[u] = i1++;

    for (auto const &[_, v, i] : g[u])
        if (!visited[v])
        {
            t[u].emplace_back(u, v, i);
            t[v].emplace_back(v, u, i);
            tie(i1, i2) = find_dfs_tree(v, i1, i2);
        }

    postorder[u] = i2++;
    return {i1, i2};
}

bool is_ancestor(size_t u, size_t v)
{
    return preorder[u] <= preorder[v] && postorder[u] >= postorder[v];
}

void find_special_edges(size_t u)
{
    visited[u] = 1;

    for (auto const &[_, v, i] : g[u])
    {
        if (!visited[v])
            find_special_edges(v);
        else
            special_edges.emplace_back(u, v, i);
    }
}

variant<bool, vector<int>> find_journey(
    int N, int M, vector<int> U, vector<int> V)
{
    for (size_t i = 0; i < M; i++)
        g[U[i]].emplace_back(U[i], V[i], i);

    find_dfs_tree(0);
    memset(visited, 0, sizeof visited);
    find_special_edges(0);

    sort(special_edges.begin(), special_edges.end(),
         [](Edge const &a, Edge const &b)
         { return is_ancestor(a.v, a.u) && !is_ancestor(b.v, b.u); });

    if (special_edges.empty() ||
        !is_ancestor(special_edges[0].v, special_edges[0].u))
        return false;

    for (size_t i = 1; i < special_edges.size(); i++)
    {
        auto const u1 = special_edges[0].u, v1 = special_edges[0].v,
                   u2 = special_edges[i].u, v2 = special_edges[i].v;

        if ((u1 == u2 && v1 == v2) || (is_ancestor(v1, u1) && is_ancestor(v2, u1)) ||
            (is_ancestor(u1, v1) && is_ancestor(u2, v1)))
            continue;

        if (is_ancestor(v2, u2) || is_ancestor(v2, u1))
        {
            vector<int> path;
            find_tree_path(0, u1, path);
            path.push_back(special_edges[0].i);
            find_tree_path(v1, u2, path);
            path.push_back(special_edges[i].i);
            find_tree_path(v2, v1, path);
            path.push_back(special_edges[0].i);
            find_tree_path(u1, v2, path);
            path.push_back(special_edges[i].i);
            find_tree_path(u2, 0, path);
            return path;
        }
    }

    return false;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:72:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     for (size_t i = 0; i < M; i++)
      |                        ~~^~~

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