Submission #796442

#	Time	Username	Problem	Language	Result	Execution time	Memory
796442		caganyanmaz	Keys (IOI21_keys)	C++17	100 / 100	844 ms	56440 KiB

keys

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

constexpr static int SIZE = 300000;
constexpr static int MX = 1e6;
vector<array<int, 2>> g[SIZE];
vector<int> pending_nodes[SIZE];
bitset<SIZE> processed;
int visited[SIZE];
int keys[SIZE];
vector<int> pending_keys;
int counts[SIZE];
vector<int> visited_list;
vector<int> r;

int min_count = MX;

int bfs(int node)
{
        queue<int> q;
        q.push(node);
        int counter = 0;
        while (q.size())
        {
                int j = q.front();
                q.pop();
                counter++;
                visited[j] = node;
                visited_list.pb(j);
                if (processed[j] || counter > min_count)
                        return MX;
                if (keys[r[j]] != node)
                {
                        keys[r[j]] = node;
                        for (int c : pending_nodes[r[j]])
                        {
                                if (visited[c] != node)
                                {
                                        visited[c] = node;
                                        q.push(c);
                                }
                        }
                }
                for (auto [c, k] : g[j])
                {
                        if (visited[c] == node)
                                continue;
                        if (keys[k] != node)
                        {
                                if (pending_nodes[k].empty())
                                        pending_keys.pb(k);
                                pending_nodes[k].pb(c);
                        }
                        else
                        {
                                visited[c] = node;
                                q.push(c);
                        }
                }
        }
        return counter;
}

void process(int node)
{
        int res = bfs(node);
        processed[node] = true;
        for (int i : pending_keys)
                pending_nodes[i].clear();
        pending_keys.clear();
        min_count = min(res, min_count);
        for (int i : visited_list)
                counts[i] = min(counts[i], res);
        visited_list.clear();
}

vector<int> find_reachable(vector<int> rr, vector<int> u, vector<int> v, vector<int> c)
{
        r = rr;
        int n = r.size(), m = u.size();
        for (int i = 0; i < m; i++)
        {
                g[v[i]].pb({u[i], c[i]});
                g[u[i]].pb({v[i], c[i]});
        }
        for (int i = 0; i < n; i++)
        {
                visited[i] = -1;
                keys[i] = -1;
                counts[i] = MX;
        }
        vector<int> ordering(2*m);
        for (int i = 0; i < m; i++)
        {
                ordering[i*2] = u[i];
                ordering[i*2+1] = v[i];
        }
        shuffle(ordering.begin(), ordering.end(), default_random_engine(42));
        for (int i : ordering)
                if (!processed[i])
                        process(i);
        for (int i = 0; i < n; i++)
                if (!processed[i])
                        process(i);
        vector<int> res(n, 0);
        for (int i = 0; i < n; i++)
                if (counts[i] == min_count)
                        res[i] = 1;
        return res;
}

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