Submission #502870

#	Time	Username	Problem	Language	Result	Execution time	Memory
502870		waynetuinfor	Keys (IOI21_keys)	C++17	37 / 100	3093 ms	25660 KiB

keys

#include <algorithm>
#include <vector>

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u,
                                std::vector<int> v, std::vector<int> c) {
  int N = r.size(), M = u.size();
  std::vector<std::vector<int>> g(N);
  std::vector<std::vector<int>> keys(N);
  for (int e = 0; e < M; ++e) {
    g[u[e]].push_back(e);
    g[v[e]].push_back(e);
    keys[c[e]].push_back(e);
  }
  std::vector<bool> vis(N);
  std::vector<bool> got(N);
  std::vector<int> p(N);
  for (int x = 0; x < N; ++x) {
    std::fill(vis.begin(), vis.end(), false);
    std::fill(got.begin(), got.end(), false);

    std::vector<int> que;

    auto Push = [&](int p) {
      if (got[p]) {
        return;
      }
      got[p] = true;
      for (int e : keys[p]) {
        if (vis[u[e]] && !vis[v[e]]) {
          vis[v[e]] = true;
          que.push_back(v[e]);
        }
        if (vis[v[e]] && !vis[u[e]]) {
          vis[u[e]] = true;
          que.push_back(u[e]);
        }
      }
    };

    vis[x] = true;
    que.push_back(x);
    for (int it = 0; it < que.size(); ++it) {
      int y = que[it];
      Push(r[y]);
      for (int e : g[y]) {
        int z = u[e] ^ v[e] ^ y;
        if (got[c[e]] && !vis[z]) {
          vis[z] = true;
          que.push_back(z);
        }
      }
    }
    p[x] = std::count(vis.begin(), vis.end(), true);
  }
  std::vector<int> res(N);
  int t = *std::min_element(p.begin(), p.end());
  for (int i = 0; i < N; ++i) {
    if (p[i] == t) {
      res[i] = 1;
    }
  }
  return res;
}

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:42:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int it = 0; it < que.size(); ++it) {
      |                      ~~~^~~~~~~~~~~~

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