Submission #437072

#	Time	Username	Problem	Language	Result	Execution time	Memory
437072		BrunoPloumhans	Keys (IOI21_keys)	C++17	37 / 100	2593 ms	59564 KiB

keys

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

int n;
vector<int> r;
vector<int> cnts;
vector<int> ans;

struct edge {
    int k;
    int v;
};

vector<vector<edge>> adj;

unordered_map<int, int> visited_sets;
vector<unordered_set<int>> setlist;
int min_count = 1e9;
vector<bool> visited;
vector<int> visited_indices;

bool a_contains_all_b(unordered_set<int>& a, vector<int>& b) {
    for(int i : b) {
        if (a.count(i) == 0) return false;
    }
    return true;
}

void compute_cnt(int start) {
    unordered_set<int> collected_keys;

    queue<int> to_visit {{ start }};
    unordered_map<int, vector<int>> next_unlocked;

    while (!to_visit.empty()) {
        int u = to_visit.front(); to_visit.pop();
        if (visited[u]) continue;
        visited[u] = true;
        visited_indices.push_back(u);
        if (cnts[u] > 0) {
            // we know what happens if we start from u
            if (cnts[u] == min_count && a_contains_all_b(setlist[visited_sets[u]], visited_indices)) {
                // u has the minimum size, check if we are inside or not
                // contains all, ok
                cnts[start] = cnts[u];
                visited_sets[start] = visited_sets[u];
            } else {
                cnts[start] = min_count+1;
            }
            break;
        }
        if (collected_keys.insert(r[u]).second) {
            for (int v : next_unlocked[r[u]]) {
                to_visit.push(v);
            }
        }

        for (edge e : adj[u]) {
            if (collected_keys.count(e.k) > 0) {
                to_visit.push(e.v);
            } else {
                next_unlocked[e.k].push_back(e.v);
            }
        }
    }

    if (cnts[start] == 0) {
        cnts[start] = visited_indices.size();
        visited_sets[start] = setlist.size();
        unordered_set<int> vis_set(visited_indices.begin(), visited_indices.end());
        setlist.push_back(move(vis_set));
        //cerr << "Full computation for start = " << start << endl;
    }
    min_count = min(cnts[start], min_count);

    for (int i : visited_indices) {
        visited[i] = false;
    }
    visited_indices.clear();
}

mt19937 gen(58);

std::vector<int> find_reachable(std::vector<int> r_, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    r = r_;
    n = r.size();
    cnts = vector<int>(r.size(), 0);
    adj.resize(n);
    visited.resize(n);
    for (int i = 0; i < u.size(); ++i) {
        adj[u[i]].push_back(edge({c[i], v[i]}));
        adj[v[i]].push_back(edge({c[i], u[i]}));
    }

    vector<int> ilist(n);
    for (int i = 0; i < n; ++i) ilist[i] = i;
    shuffle(ilist.begin(), ilist.end(), gen);


    for (int i : ilist) {
        compute_cnt(i);
    }

    ans = vector<int>(n, 0);
    for (int i = 0; i < n; ++i) {
        ans[i] = cnts[i] == min_count;
    }
    return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < u.size(); ++i) {
      |                     ~~^~~~~~~~~~

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