Submission #795982

#	Time	Username	Problem	Language	Result	Execution time	Memory
795982		MattTheNub	Keys (IOI21_keys)	C++17	9 / 100	444 ms	140144 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <class T> using v = vector<T>;
#ifdef EVAL
#define dbg(...)
#define dbg2d(...)
#else
istream &__cin = cin;
#include "../../debug.h"
__cinwrapper __cin_wrapper;
#include "../../debug.cpp"
#endif
#include <vector>

#define f first
#define s second
using ll = long long;
using int2 = pair<int, int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct chash {
  static const int RANDOM;
  static unsigned hash_f(uint64_t x) {
    x += RANDOM;
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static unsigned hash_comb(unsigned a, unsigned b) {
    return hash_f(a * 31 + b);
  }
  int operator()(int x) const { return hash_f(x); }
  int operator()(ll x) const { return hash_f(x); }
  template <class T1, class T2> int operator()(pair<T1, T2> x) const {
    return hash_comb((*this)(x.f), (*this)(x.s));
  }
  int operator()(const string &s) const {
    int hash = 0;
    for (char c : s) {
      hash = hash_comb(c, hash);
    }
    return hash;
  }
};
const int chash::RANDOM = rng();

template <class K, class V> using ht = gp_hash_table<K, V, chash>;
template <class T> using hs = gp_hash_table<T, null_type, chash>;

struct Edg {
  int u, v, c, i;
  friend bool operator<(Edg a, Edg b) {
    return (a.c == b.c) ? (a.i < b.i) : (a.c < b.c);
  }
};
queue<Edg> nxt;
v<int2> vis;

struct DSU {
  v<int> e;
  v<hs<int>> keys;
  v<set<Edg>> edg;
  DSU(int n) : keys(n), edg(n) { e = v<int>(n, -1); }

  int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
  bool same_set(int a, int b) { return get(a) == get(b); }
  int size(int x) { return -e[get(x)]; }

  bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) {
      return false;
    }
    if (e[x] > e[y]) {
      swap(x, y);
    }
    e[x] += e[y];
    e[y] = x;
    if (edg[y].size() + keys[y].size() > edg[x].size() + keys[x].size()) {
      keys[y].swap(keys[x]);
      edg[y].swap(edg[x]);
    }
    for (auto z : keys[y]) {
      auto it = edg[x].lower_bound({0, 0, z, -1});
      while (it != edg[x].end() && it->c == z) {
        nxt.push(*it);
        it++;
        edg[x].erase(prev(it));
      }
      keys[x].insert(z);
    }
    for (auto z : edg[y]) {
      if (keys[x].find(z.c) != keys[x].end()) {
        nxt.push(z);
      } else {
        edg[y].insert(z);
      }
    }
    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 = r.size();
  int m = u.size();
  DSU dsu(n);

  vis.assign(m, {-1, -1});

  for (int i = 0; i < m; i++) {
    dsu.edg[u[i]].insert({u[i], v[i], c[i], i});
    dsu.edg[v[i]].insert({v[i], u[i], c[i], i});

    if (r[u[i]] == c[i]) {
      nxt.push({u[i], v[i], c[i], i});
    }
    if (r[v[i]] == c[i]) {
      nxt.push({v[i], u[i], c[i], i});
    }
  }
  for (int i = 0; i < n; i++) {
    dsu.keys[i].insert(r[i]);
  }

  while (nxt.size()) {
    Edg edg = nxt.front();
    nxt.pop();

    if (vis[edg.i].s != -1 || vis[edg.i].f == edg.u)
      continue;
    else if (vis[edg.i].f == -1) {
      dbg(edg.u, edg.v);
      vis[edg.i].f = edg.u;
    } else {
      dbg(edg.u, edg.v);
      vis[edg.i].s = edg.u;
      dsu.unite(edg.u, edg.v);
    }
  }
  dbg(vis);

  hs<int> components;
  for (int i = 0; i < n; i++) {
    components.insert(dsu.get(i));
  }

  for (int i = 0; i < m; i++) {
    if (vis[i].s == -1 && vis[i].f != -1) {
      components.erase(dsu.get(vis[i].f));
    }
  }

  int mn = INT_MAX;
  for (auto x : components) {
    mn = min(mn, dsu.size(x));
  }

  hs<int> componentstoo;
  for (auto x : components) {
    if (dsu.size(x) == mn) {
      componentstoo.insert(x);
    }
  }
  vector<int> ans(n, 0);
  for (int i = 0; i < n; i++) {
    if (componentstoo.find(dsu.get(i)) != componentstoo.end()) {
      ans[i] = 1;
    }
  }

  return ans;
}

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