Submission #823950

#	Time	Username	Problem	Language	Result	Execution time	Memory
823950		finn__	Thousands Islands (IOI22_islands)	C++17	35 / 100	287 ms	49720 KiB

islands

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

constexpr int N_MAX = 100000;

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

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

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;
    while (g[x].size() == 1)
    {
        int y = g[x].begin()->first;
        delete_node(x);
        x = y;
    }

    return !g[x].empty();
}

• Subtask 1: 1.75 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 7.35 / 21
• Subtask 4: 8.399999999999999 / 24
• Subtask 5: 15.749999999999998 / 45