Submission #824028

#	Time	Username	Problem	Language	Result	Execution time	Memory
824028		finn__	Thousands Islands (IOI22_islands)	C++17	100 / 100	284 ms	48784 KiB

islands

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

constexpr int N_MAX = 100000;

set<pair<int, int>> g[N_MAX], rg[N_MAX];
bitset<N_MAX> visited, in_dfs;

void delete_node(int u)
{
    vector<int> to_delete;
    for (auto const &[v, i] : g[u])
        rg[v].erase(make_pair(u, i));
    for (auto const &[v, i] : rg[u])
    {
        g[v].erase(make_pair(u, i));
        if (g[v].empty())
            to_delete.push_back(v);
    }
    g[u].clear();
    rg[u].clear();

    for (auto const &v : to_delete)
        delete_node(v);
}

int find_cycle(int u, vector<int> &cycle, vector<int> &path_to_cycle)
{
    if (in_dfs[u])
        return u;
    if (visited[u])
        return -1;

    visited[u] = 1;
    in_dfs[u] = 1;

    for (auto const &[v, i] : g[u])
    {
        int x = find_cycle(v, cycle, path_to_cycle);
        if (x != -1)
        {
            cycle.push_back(i);
            in_dfs[u] = 0;
            return u == x ? -1 : x;
        }
        else if (!cycle.empty())
        {
            path_to_cycle.push_back(i);
            in_dfs[u] = 0;
            return -1;
        }
    }

    in_dfs[u] = 0;
    return -1;
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
    for (int i = 0; i < M; ++i)
        g[U[i]].emplace(V[i], i), rg[V[i]].emplace(U[i], i);
    for (int i = 0; i < N; ++i)
        if (g[i].empty())
            delete_node(i);

    int x = 0;
    vector<int> line;
    while (g[x].size() == 1)
    {
        int y = g[x].begin()->first;
        line.push_back(g[x].begin()->second);
        delete_node(x);
        x = y;
    }

    if (g[x].empty())
        return false;

    vector<int> cycle_a, path_to_cycle_a, cycle_b, path_to_cycle_b;
    find_cycle(x, cycle_a, path_to_cycle_a);
    visited.reset();
    g[x].erase(g[x].begin());
    find_cycle(x, cycle_b, path_to_cycle_b);
    assert(!cycle_a.empty() && !cycle_b.empty());

    reverse(cycle_a.begin(), cycle_a.end());
    reverse(cycle_b.begin(), cycle_b.end());
    reverse(path_to_cycle_a.begin(), path_to_cycle_a.end());
    reverse(path_to_cycle_b.begin(), path_to_cycle_b.end());

    vector<int> cycle_a_ind(M, -1);
    for (int i = 0; i < cycle_a.size(); ++i)
        cycle_a_ind[cycle_a[i]] = i;

    int common_a = -1, common_b = -1;
    for (int i = 0; i < cycle_b.size(); ++i)
        if (cycle_a_ind[cycle_b[i]] != -1)
        {
            common_a = cycle_a_ind[cycle_b[i]];
            common_b = i;
            break;
        }

    vector<int> tour = line;
    if (common_a == -1)
    {
        tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
        tour.insert(tour.end(), cycle_a.begin(), cycle_a.end());
        tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
        reverse(tour.end() - path_to_cycle_a.size(), tour.end());

        tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
        tour.insert(tour.end(), cycle_b.begin(), cycle_b.end());
        tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
        reverse(tour.end() - path_to_cycle_b.size(), tour.end());

        tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
        tour.insert(tour.end(), cycle_a.begin(), cycle_a.end());
        reverse(tour.end() - cycle_a.size(), tour.end());
        tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
        reverse(tour.end() - path_to_cycle_a.size(), tour.end());

        tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
        tour.insert(tour.end(), cycle_b.begin(), cycle_b.end());
        reverse(tour.end() - cycle_b.size(), tour.end());
        tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
        reverse(tour.end() - path_to_cycle_b.size(), tour.end());
    }
    else
    {
        tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
        tour.insert(tour.end(), cycle_a.begin(), cycle_a.end());
        tour.insert(tour.end(), path_to_cycle_a.begin(), path_to_cycle_a.end());
        reverse(tour.end() - path_to_cycle_a.size(), tour.end());

        tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
        tour.insert(tour.end(), cycle_b.begin(), cycle_b.begin() + common_b);

        rotate(cycle_a.begin(), cycle_a.begin() + common_a, cycle_a.end());
        tour.insert(tour.end(), cycle_a.begin(), cycle_a.end());
        reverse(tour.end() - cycle_a.size(), tour.end());

        tour.insert(tour.end(), cycle_b.begin(), cycle_b.begin() + common_b);
        reverse(tour.end() - common_b, tour.end());
        tour.insert(tour.end(), path_to_cycle_b.begin(), path_to_cycle_b.end());
        reverse(tour.end() - path_to_cycle_b.size(), tour.end());
    }

    tour.insert(tour.end(), line.begin(), line.end());
    reverse(tour.end() - line.size(), tour.end());

    return tour;
}

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:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < cycle_a.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~
islands.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int i = 0; i < cycle_b.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~

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