Submission #1202677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202677		LucaLucaM	Keys (IOI21_keys)	C++20	37 / 100	3095 ms	42000 KiB

keys

#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <queue>
#include <random>

std::mt19937 rng(123);

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = (int) r.size();

  std::vector<bool> haveKey(n, false);
  std::vector<std::vector<int>> unlock(n);
  std::vector<bool> explored(n, false);
  std::vector<bool> vis(n, false);

  int m = (int) u.size();
  std::vector<std::vector<std::pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    g[u[i]].push_back({v[i], c[i]});
    g[v[i]].push_back({u[i], c[i]});
  }
  
  std::vector<int> answer(n, n + 1);

  auto explore = [&](int start) { // un din asta am voie sa fac in O(n)
    std::queue<int> reach; // nu cred ca e neaparat sa fac bfs dar trebuie sa resetez niste chestii la final si atunci cand fac bfs pot doar sa dau break si se amortizeaza sau ceva
    reach.push(start);
    vis[start] = true;
    std::vector<int> visited;
    bool early = false;
    while (!reach.empty()) {
      int u = reach.front();
      visited.push_back(u);
      reach.pop();
      if (explored[u]) {
        early = true; 
        break;
      }
      int key = r[u];
      for (const auto &[v, t] : g[u]) {
        if (!vis[v]) {
          if (haveKey[t]) {
            reach.push(v);
            vis[v] = true;
          } else { 
            unlock[t].push_back(v);
          }
        }
      }
      if (haveKey[key]) {
        continue;
      }
      haveKey[key] = true;
      for (const auto &u : unlock[key]) {
        if (!vis[u]) {
          vis[u] = true;
          reach.push(u);
        }
      }
      unlock[key].clear();
    }


    if (!early) {
      for (int u : visited) {
        answer[u] = std::min(answer[u], (int) visited.size());
      }
    } else {
      while (!reach.empty()) {
        vis[reach.front()] = false;
        reach.pop();
      }
    }
    for (int u : visited) {
      vis[u] = false;
      haveKey[r[u]] = false;
      for (const auto &[v, t] : g[u]) {
        unlock[t].clear();
      }
    }
    explored[start] = true;
  };

  int mini = n + 1;
  std::vector<int> order(n);
  for (int i = 0; i < n; i++) {
    order[i] = i;
  }
  std::shuffle(order.begin(), order.end(), rng);
  for (int u : order) {
    explore(u);
  }
  
  for (int i = 0; i < n; i++) {
    mini = std::min(mini, answer[i]);
  }
  
  std::vector<int> ret(n);
  for (int i = 0; i < n; i++) {
    ret[i] = (answer[i] == mini);
  }

	return ret;
}

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