Submission #799722

#	Time	Username	Problem	Language	Result	Execution time	Memory
799722		finn__	Keys (IOI21_keys)	C++17	100 / 100	803 ms	157904 KiB

keys

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

constexpr size_t N = 300000;

vector<uint32_t> g[N], scc[N], cycle;
unordered_map<uint32_t, vector<uint32_t>> edges[N];
set<uint32_t> keys[N];
bitset<N> visited, in_dfs_path, is_leaf;
uint32_t scc_index[N];

uint32_t dfs(size_t u)
{
    if (in_dfs_path[u]) // SCC found
        return u;
    visited[u] = 1;
    in_dfs_path[u] = 1;

    while (!g[u].empty())
    {
        uint32_t v = scc_index[g[u][0]];
        swap(g[u][0], g[u].back());
        g[u].pop_back();

        uint32_t x = dfs(v);

        if (x != UINT32_MAX)
        {
            cycle.push_back(u);
            if (x == u) // backtracked until the start of the cycle
            {
                uint32_t main = u;
                for (auto const &w : cycle)
                    if (scc[w].size() > scc[main].size())
                        main = w;

                in_dfs_path[u] = 0;
                in_dfs_path[main] = 1;
                u = main;
                cycle.erase(find(cycle.begin(), cycle.end(), main));

                for (auto const &w : cycle)
                {
                    scc[u].insert(scc[u].end(), scc[w].begin(), scc[w].end());
                    for (auto const &y : scc[w])
                        scc_index[y] = u;
                    scc[w].clear();
                    g[u].insert(g[u].end(), g[w].begin(), g[w].end());

                    is_leaf[u] = is_leaf[u] && is_leaf[w];
                    keys[u].insert(keys[w].begin(), keys[w].end());

                    for (auto const &c : keys[w])
                    {
                        auto it = edges[u].find(c);
                        if (it != edges[u].end())
                        {
                            g[u].insert(g[u].end(), it->second.begin(), it->second.end());
                            it->second.clear();
                        }
                    }
                }
                for (auto const &w : cycle)
                {
                    for (auto const &[c, e] : edges[w])
                        if (keys[u].find(c) != keys[u].end())
                            g[u].insert(g[u].end(), e.begin(), e.end());
                        else
                            edges[u][c].insert(edges[u][c].end(), e.begin(), e.end());
                }

                cycle.clear();
            }
            else
            {
                in_dfs_path[u] = 0;
                return x;
            }
        }
        else
        {
            is_leaf[u] = 0;
        }
    }

    in_dfs_path[u] = 0;
    return UINT32_MAX;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    size_t const n = r.size();

    for (size_t i = 0; i < u.size(); ++i)
    {
        visited[u[i]] = visited[u[i]] || c[i] == r[u[i]];
        visited[v[i]] = visited[v[i]] || c[i] == r[v[i]];
    }
    if (visited.count() < n)
    {
        vector<int> ans(n);
        for (size_t i = 0; i < n; ++i)
            ans[i] = !visited[i];
        return ans;
    }
    visited.reset();

    for (size_t i = 0; i < n; ++i)
        keys[i].insert(r[i]), scc[i].push_back(i);

    for (size_t i = 0; i < u.size(); ++i)
    {
        if (c[i] == r[u[i]])
            g[u[i]].push_back(v[i]);
        else
            edges[u[i]][c[i]].push_back(v[i]);

        if (c[i] == r[v[i]])
            g[v[i]].push_back(u[i]);
        else
            edges[v[i]][c[i]].push_back(u[i]);
    }

    iota(scc_index, scc_index + N, 0);
    for (size_t i = 0; i < n; ++i)
        is_leaf[i] = 1;
    for (size_t i = 0; i < n; ++i)
        if (!visited[i])
            dfs(i);

    size_t smallest = SIZE_MAX;
    for (size_t i = 0; i < n; ++i)
        if (is_leaf[i] && scc[i].size())
            smallest = min(smallest, scc[i].size());
    vector<int> ans(n);
    for (size_t i = 0; i < n; ++i)
        if (is_leaf[i] && scc[i].size() == smallest)
            for (auto const &u : scc[i])
                ans[u] = 1;
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33