Submission #795632

#	Time	Username	Problem	Language	Result	Execution time	Memory
795632		caganyanmaz	Keys (IOI21_keys)	C++17	37 / 100	3061 ms	37856 KiB

keys

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

constexpr static int SIZE = 300000;
vector<array<int, 2>> g[SIZE];
set<array<int, 2>> pending_edges;
int visited[SIZE];
int keys[SIZE];
int counts[SIZE];
vector<int> r;

int min_count = INT_MAX;
int current_node;

bool dfs(int node)
{
        counts[current_node]++;
        visited[node] = current_node;
        if (counts[node] > min_count)
                counts[current_node] = INT_MAX;
        if (counts[current_node] > min_count)
                return false;
        int key = r[node];
        if (keys[key] != current_node)
        {
                keys[key] = current_node;
                array<int, 2> sss = {key, 0};
                for (auto it = pending_edges.lower_bound(sss); it != pending_edges.end() && (*it)[0] == key; it++)
                        if (visited[(*it)[1]] != current_node && !dfs((*it)[1]))
                                return false;
        }

        for (auto [c, k] : g[node])
        {
                if (visited[c] == current_node)
                        continue;
                if (keys[k] == current_node)
                {
                        if(!dfs(c))
                                return false;
                }
                else
                {
                        pending_edges.insert({k, c});
                }
        }
        return true;
}

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]});
        }
        int min_count = n;
        for (int i = 0; i < n; i++)
        {
                visited[i] = -1;
                keys[i] = -1;
        }
        vector<int> ordering(n);
        for (int i = 0; i < n; i++)
                ordering[i] = i;
        for (int i = 0; i < n; i++)
        {
                int j = rand() % (i+1);
                swap(ordering[i], ordering[j]);
        }

        for (int i : ordering)
        {
                current_node = i;
                pending_edges.clear();
                dfs(i);
                min_count = min(min_count, counts[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: 0 / 30
• Subtask 5: 0 / 33