Submission #503071

#	Time	Username	Problem	Language	Result	Execution time	Memory
503071		waynetuinfor	Keys (IOI21_keys)	C++17	100 / 100	1392 ms	214276 KiB

keys

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <vector>

struct UnionFind {
  UnionFind(int n) : uf(n) { std::iota(uf.begin(), uf.end(), 0); }

  int Find(int x) {
    if (x == uf[x]) return x;
    return uf[x] = Find(uf[x]);
  }

  void Merge(int x, int y) {
    int fx = Find(x), fy = Find(y);
    uf[fx] = fy;
  }

  std::vector<int> uf;
};

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::unordered_set<int>> keys(N + N);
  std::vector<std::unordered_map<int, std::vector<int>>> out_edges(N + N);
  std::vector<std::vector<int>> good_edges(N + N);
  std::vector<int> sz_v(N + N), sz_e(N + N);
  std::vector<int> to(N + N, -1);
  for (int i = 0; i < N; ++i) {
    keys[i].insert(r[i]);
    sz_v[i] = 1;
  }
  for (int i = 0; i < M; ++i) {
    for (int x : {u[i], v[i]}) {
      sz_e[x]++;
      if (r[x] == c[i]) {
        good_edges[x].push_back(i);
      } else {
        out_edges[x][c[i]].push_back(i);
      }
    }
  }
  int K = N;
  UnionFind conn(N + N), repr(N + N);
  std::vector<int> res;
  for (int i = 0; i < K; ++i) {
    while (!good_edges[i].empty()) {
      int e = good_edges[i].back();
      if (repr.Find(u[e]) == repr.Find(v[e])) {
        good_edges[i].pop_back();
      } else {
        break;
      }
    }
    if (good_edges[i].empty()) {
      // std::cerr << "stop i = " << i << "\n";
      res.push_back(i);
      continue;
    }
    int e = good_edges[i].back();
    int x = repr.Find(u[e]), y = repr.Find(v[e]);
    assert(x == i || y == i);
    if (x != i) {
      std::swap(x, y);
    }
    // std::cerr << "x = " << x << " y = " << y << std::endl;
    to[x] = y;
    if (conn.Find(x) == conn.Find(y)) {
      std::vector<int> cycle;
      int t = i;
      do {
        // std::cerr << "t = " << t << std::endl;
        cycle.push_back(t);
        assert(to[t] != -1);
        t = repr.Find(to[t]);
      } while (t != i);
      int p = K++;
      for (int t : cycle) {
        conn.Merge(t, p);
        sz_v[p] += sz_v[t];
        if (sz_e[p] < sz_e[t]) {
          keys[p].swap(keys[t]);
          out_edges[p].swap(out_edges[t]);
          good_edges[p].swap(good_edges[t]);
        }
        sz_e[p] += sz_e[t];
        good_edges[p].insert(good_edges[p].end(), good_edges[t].begin(),
                             good_edges[t].end());
        for (int k : keys[t]) {
          if (keys[p].find(k) == keys[p].end()) {
            keys[p].insert(k);
            if (out_edges[p].find(k) != out_edges[p].end()) {
              good_edges[p].insert(good_edges[p].end(), out_edges[p][k].begin(),
                                   out_edges[p][k].end());
              out_edges[p].erase(k);
            }
          }
        }
        for (auto iter : out_edges[t]) {
          int k = iter.first;
          if (keys[p].find(k) != keys[p].end()) {
            good_edges[p].insert(good_edges[p].end(), iter.second.begin(),
                                 iter.second.end());
          } else {
            out_edges[p][k].insert(out_edges[p][k].end(), iter.second.begin(),
                                   iter.second.end());
          }
        }
        repr.Merge(t, p);
      }
    } else {
      conn.Merge(x, y);
    }
  }
  int min_sz = N + 1;
  for (int u : res) {
    assert(repr.Find(u) == u);
    min_sz = std::min(min_sz, sz_v[u]);
  }
  std::vector<bool> opt(N + N);
  for (int u : res) {
    if (sz_v[u] == min_sz) {
      opt[u] = true;
    }
  }
  std::vector<int> ans(N);
  for (int i = 0; i < N; ++i) {
    if (opt[repr.Find(i)]) {
      ans[i] = 1;
    }
  }
  return ans;
}

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