Submission #712493

#	Time	Username	Problem	Language	Result	Execution time	Memory
712493		danikoynov	Keys (IOI21_keys)	C++17	100 / 100	1345 ms	253252 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"

using namespace std;


const int maxn = 3e5 + 10;


struct union_find
{
    vector < int > data, rnk;

    union_find(int n)
    {
        data.resize(n);
        rnk.resize(n);
        for (int i = 0; i < n; i ++)
        {
            data[i] = i;
            rnk[i] = 1;
        }
    }
    int find_leader(int v)
    {
        return (v == data[v]) ? v : (data[v] = find_leader(data[v]));
    }

    int unite(int v, int u)
    {
        v = find_leader(v);
        u = find_leader(u);
        if (v != u)
        {
            if (rnk[v] < rnk[u])
                swap(v, u);
            rnk[v] += rnk[u];
            data[u] = v;
        }
        return v;
    }
};

struct component
{
    vector < int > open;
    map < int, vector < int > > locked;
    set < int > keys;

    void add_edge(int v, int key)
    {
        if (keys.find(key) != keys.end())
            open.push_back(v);
        else
            locked[key].push_back(v);
    }

    void add_key(int key)
    {
        while(!locked[key].empty())
        {
            open.push_back(locked[key].back());
            locked[key].pop_back();
        }
        keys.insert(key);
    }
};

int n, m;
int status[maxn], toward[maxn], reach[maxn];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    n = r.size();
    m = u.size();
    for (int i = 0; i < n; i ++)
        reach[i] = n + 1;
    union_find dsu(n);
    vector < component > data(n);
    for (int i = 0; i < n; i ++)
    data[i].add_key(r[i]);
    for (int i = 0; i < m; i ++)
    {
        data[u[i]].add_edge(v[i], c[i]);
        data[v[i]].add_edge(u[i], c[i]);
    }

    for (int cur = 0; cur < n; cur ++)
    {
        if (status[cur] == 1)
            continue;

        vector < int > ver_list;
        int u = cur;
        while(status[u] != 1)
        {
            if (status[u] == 0)
            {
                status[u] = -1;
                ver_list.push_back(u);
            }

            if (data[u].open.empty())
            {
                vector < int > same;
                for (int v : ver_list)
                    if (dsu.find_leader(v) == u)
                    same.push_back(v);
                for (int v : same)
                    reach[v] = same.size();
                break;
            }

            toward[u] = dsu.find_leader(data[u].open.back());
            data[u].open.pop_back();

            if (status[toward[u]] == -1)
            {
                int v = u;
                while(true)
                {
                    v = dsu.find_leader(toward[v]);
                    if (v == u)
                        break;

                    int r = dsu.unite(u, v);
                    int to_move = u;
                    if (r == u)
                        to_move = v;
                    u = r;
                    for (int x : data[to_move].open)
                        data[u].open.push_back(x);

                    for (int x : data[to_move].keys)
                        data[u].add_key(x);

                    for (pair < int, vector < int > > it : data[to_move].locked)
                    {
                        for (int x : it.second)
                            data[u].add_edge(x, it.first);
                    }
                }
            }
            else
            {
                u = toward[u];
            }
        }
        for (int v : ver_list)
            status[v] = 1;
    }

    int min_reach = n + 1;
    for (int i = 0; i < n; i ++)
        min_reach = min(min_reach, reach[i]);
    vector < int > ans(n, 0);
    for (int i = 0; i < n; i ++)
    {
            ans[i] = (reach[i] == min_reach);
    }
    return ans;
}

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