Submission #831510

#	Time	Username	Problem	Language	Result	Execution time	Memory
831510		erray	Keys (IOI21_keys)	C++17	100 / 100	1314 ms	55164 KiB

keys

#include <vector>
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/eagle/ioi22/d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

struct DSU {
  vector<int> link;
  DSU(int n) {
    link.resize(n);
    iota(link.begin(), link.end(), 0);
  }
  int get(int v) {
    return link[v] = (link[v] != v ? get(link[v]) : v);
  }
  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) {
      return false;
    }
    link[y] = x;
    return true;
  }
};

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());
  int M = int(U.size());
  vector<vector<int>> g(N);
  for (int i = 0; i < M; ++i) {
    g[V[i]].push_back(i);
    g[U[i]].push_back(i);
  }
  DSU d(N);
  vector<bool> act(N);
  vector<bool> vis(N);
  vector<vector<int>> blocked(N);
  auto Expand = [&](int x) -> pair<vector<int>, int> {
    int link = -1;
    vector<int> verts;
    auto Add_v = [&](int to) {
      if (d.get(to) != d.get(x)) {
        link = d.get(to);
      } else if (!vis[to]) {
        verts.push_back(to);
        vis[to] = true;
        act[R[to]] = true;
      }
    };
    auto Add_e = [&](int id) {
      Add_v(V[id]);
      Add_v(U[id]);
    };
    Add_v(x);
    for (int it = 0; it < int(verts.size()); ++it) {
      int v = verts[it];
      Add_v(v);
      for (auto e : blocked[R[v]]) {
        Add_e(e);
      }
      blocked[R[v]].clear();
      for (auto id : g[v]) {
        if (act[C[id]]) {
          Add_e(id);
        } else {
          blocked[C[id]].push_back(id);
        }
      } 
    }
    for (auto v : verts) {
      act[R[v]] = false;
      vis[v] = false;
      for (auto id : g[v]) {
        blocked[C[id]].clear(); 
      }
    }
    return {verts, link};
  };
  while (true) {
    vector<array<int, 2>> upd;
    for (int i = 0; i < N; ++i) {
      if (d.get(i) == i) {
        auto[v, x] = Expand(i);
        if (x != -1) {
          upd.push_back({x, i});
        }
      }
    }
    for (auto[x, v] : upd) {
      d.unite(x, v);
    }
    if (upd.empty()) {
      break;
    }
  }
  vector<int> ans;
  int mn = N + 1;
  for (int i = 0; i < N; ++i) {
    if (d.get(i) == i) {
      auto v = Expand(i).first;
      int s = int(v.size());
      if (s < mn) {
        ans.clear();
        mn = s;
      }
      if (s == mn) {
        ans.insert(ans.end(), v.begin(), v.end());
      }
    }  
  }
  vector<int> ret(N);
  for (auto v : ans) {
    ret[v] = true;
  }
  return ret;
}

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