Submission #1020493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020493		NeroZein	Keys (IOI21_keys)	C++17	37 / 100	3069 ms	28220 KiB

keys

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

vector<int> find_reachable(vector<int> city_key, vector<int> u_, vector<int> v_, vector<int> c) {
  int n = (int) city_key.size();
  int m = (int) u_.size();
  vector<int> reachable(n); 
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    int u = u_[i], v = v_[i], edge_key = c[i];
    g[u].emplace_back(v, edge_key);
    g[v].emplace_back(u, edge_key);
  }
  int mn = n;
  vector<int> ans(city_key.size(), 1);
  for (int i = 0; i < n; ++i) {
    queue<int> que; 
    que.push(i);
    vector<bool> vis(n), have(n);
    vis[i] = true;
    vector<vector<int>> tounlock(n);
    while (!que.empty()) {
      int v = que.front();
      que.pop();
      reachable[i]++; 
      if (!have[city_key[v]]) {
        have[city_key[v]] = true;
        for (int u : tounlock[city_key[v]]) {
          if (!vis[u]) {
            que.push(u);
            vis[u] = true;
          }
        }
      }
      
      for (auto [u, edge_key] : g[v]) {
        if (vis[u]) {
          continue;
        }
        if (have[edge_key]) {
          vis[u] = true;
          que.push(u); 
        } else {
          tounlock[edge_key].push_back(u); 
        }
      }
      
    }
    mn = min(mn, reachable[i]);
  }
  for (int i = 0; i < n; ++i) {
    if (reachable[i] > mn) {
      ans[i] = 0; 
    }
  }
  return ans;
}

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