Submission #1304166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304166		rxlfd314	Keys (IOI21_keys)	C++17	100 / 100	2055 ms	59096 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

struct DSU {
  vt<int> uf, root;
  DSU(const int n) : uf(n, -1), root(n) { iota(all(root), 0); }
  int find(const int i) { return uf[i] < 0 ? i : uf[i] = find(uf[i]); }
  int get_root(const int i) { return root[find(i)]; }
  void unite(int a, int b) {
    if ((a = find(a)) == (b = find(b)))
      return;
    if (uf[a] > uf[b])
      swap(a, b), swap(root[a], root[b]);
    uf[a] += uf[b];
    uf[b] = a;
    root[b] = root[a];
  }
};

vt<int> find_reachable(const vt<int> R, const vt<int> U, const vt<int> V, const vt<int> C) {
  const int N = size(R), M = size(U);
  vt<vt<ari2>> adj(N);
  FOR(i, 0, M - 1) {
    adj[U[i]].push_back({V[i], C[i]});
    adj[V[i]].push_back({U[i], C[i]});
  }
  DSU uf(N);
  bool flag = true;
  unordered_set<int> ans, p_ans;
  const auto check = [&](const int x, const bool ret_option) {
    unordered_set<int> seen, key;
    unordered_map<int, vt<int>> blocked;
    queue<int> qu;
    qu.push(x);
    seen.insert(x);
    key.insert(R[x]);
    while (size(qu)) {
      const int i = qu.front();
      qu.pop();
      if (!ret_option)
        p_ans.insert(i);
      for (const auto &[j, c] : adj[i]) {
        if (seen.count(j))
          continue;
        if (key.count(c)) {
          if (uf.find(j) != uf.find(x)) {
            assert(ret_option);
            return uf.find(j);
          }
          qu.push(j);
          seen.insert(j);
          key.insert(R[j]);
        } else {
          blocked[c].push_back(j);
        }
      }
      for (const auto &j : blocked[R[i]])
        if (!seen.count(j)) {
          if (uf.find(j) != uf.find(x)) {
            assert(ret_option);
            return uf.find(j);
          }
          seen.insert(j);
          key.insert(R[j]);
          qu.push(j);
        }
      blocked.erase(blocked.find(R[i]));
    }
    return -1;
  };
  while (flag) {
    flag = false;
    vt<ari2> pairs;
    FOR(i, 0, N - 1) {
      if (uf.get_root(i) != i)
        continue;
      const int j = check(i, 1);
      if (j >= 0)
        pairs.push_back({i, j}), flag = true;
    }
    for (const auto &[a, b] : pairs)
      uf.unite(b, a);
  }
  int cur = INT_MAX;
  FOR(i, 0, N - 1) {
    if (uf.get_root(i) != i)
      continue;
    check(i, 0);
    if (size(p_ans) < cur)
      ans.clear();
    if (size(p_ans) <= cur)
      cur = size(p_ans), ans.insert(all(p_ans));
    p_ans.clear();
  }
  vt<int> ret(N);
  for (const auto &i : ans)
    ret[i] = 1;
  return ret;
}

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