Submission #1039032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039032		spacewalker	Keys (IOI21_keys)	C++17	37 / 100	3043 ms	33960 KiB

keys

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

int reachable_count(const vector<vector<pair<int, int>>> graph, const vector<int> keys, int s) {
  int n = graph.size();

  map<int, bool> hasKey;
  map<int, vector<int>> pending;
  queue<int> q; q.push(s);

  auto markKey = [&] (int i) {
    hasKey[i] = true;
    if (pending.count(i) > 0) {
      for (int v : pending[i]) q.push(v);
      pending[i].clear();
    }
  };

  auto processEdge = [&] (int c, int to) {
    if (hasKey[c]) q.push(to);
    else pending[c].push_back(to);
  };

  vector<bool> vis(n, false);
  while (!q.empty()) {
    int cur = q.front(); q.pop();
    if (vis[cur]) continue;
    vis[cur] = true;
    markKey(keys[cur]);
    for (auto [v, c] : graph[cur]) processEdge(c, v);
  }
  return count(begin(vis), end(vis), true);
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
  int n = r.size(), m = u.size();
  vector<vector<pair<int, int>>> graph(n);
  for (int i = 0; i < m; ++i) {
    graph[u[i]].emplace_back(v[i], c[i]);
    graph[v[i]].emplace_back(u[i], c[i]);
  }

  vector<int> reachable(n);
  for (int i = 0; i < n; ++i) reachable[i] = reachable_count(graph, r, i);
  int min_scc = *min_element(begin(reachable), end(reachable));
  vector<int> ans(n);
  for (int i = 0; i < n; ++i) ans[i] = (reachable[i] == min_scc);
	return ans;
}

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