Submission #436966

#	Time	Username	Problem	Language	Result	Execution time	Memory
436966		BrunoPloumhans	Keys (IOI21_keys)	C++17	37 / 100	2586 ms	25712 KiB

keys

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

int n;
vector<int> r;
vector<int> cnts;
vector<int> ans;
int min_count = 1e9;

struct edge {
    int k;
    int v;
};

vector<vector<edge>> adj;

void compute_cnt(int start) {
    unordered_set<int> vis;
    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 (vis.count(u) > 0) continue;
        vis.insert(u);
        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);
            }
        }
    }

    cnts[start] = vis.size();
    min_count = min(cnts[start], min_count);
}

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);
    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]}));
    }

    for (int i = 0; i < r.size(); ++i) {
        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:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < u.size(); ++i) {
      |                     ~~^~~~~~~~~~
keys.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < r.size(); ++i) {
      |                     ~~^~~~~~~~~~

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