Submission #795575

#	Time	Username	Problem	Language	Result	Execution time	Memory
795575		caganyanmaz	Keys (IOI21_keys)	C++17	0 / 100	3 ms	7252 KiB

keys

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


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

int sum = 0;

bool dfs(int node)
{
        sum++;
        if (counts[node] > min_count || sum > min_count)
        {
                sum = SIZE + 1;
                return false;
        }
        visited[node] = current_node;
        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;
}

void find_count(int node)
{
        current_node = node;
        sum = 0;
        pending_edges.clear();
        dfs(node);
        counts[node] = sum;
        min_count = min(min_count, counts[node]);
}


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;
        }
        for (int i = 0; i < n; i++)
                find_count(i);
        vector<int> res(n);

        for (int i = 0; i < n; i++)
                if (counts[i] == min_count)
                        res[i] = 1;
        return res;
}

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