Submission #823574

#	Time	Username	Problem	Language	Result	Execution time	Memory
823574		finn__	Thousands Islands (IOI22_islands)	C++17	26 / 100	129 ms	29432 KiB

islands

#include <bits/stdc++.h>

#include "islands.h"

using namespace std;

constexpr size_t N_MAX = 100000;

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

void delete_node(int u)
{
    for (auto const &[v, i] : rg[u])
        g[v].erase(make_pair(u, i));
    for (auto const &[v, i] : g[u])
        rg[v].erase(make_pair(u, i));
    g[u].clear();
    rg[u].clear();
}

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);

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

    if (g[x].empty())
    {
        return false;
    }
    else
    {
        int a = g[x].begin()->second,
            b = g[g[x].begin()->first].lower_bound(make_pair(x, 0))->second,
            c = (++g[x].begin())->second,
            d = g[(++g[x].begin())->first].lower_bound(make_pair(x, 0))->second;

        int line_len = tour.size();

        if (b != d)
            tour.insert(tour.end(), {a, b, c, d, b, a, d, c});
        else
            tour.insert(tour.end(), {a, b, c, a, b, c});

        tour.resize(tour.size() + line_len);
        copy(tour.begin(), tour.begin() + line_len, tour.end() - line_len);
        reverse(tour.end() - line_len, tour.end());
        return tour;
    }
}

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