Submission #435737

#	Time	Username	Problem	Language	Result	Execution time	Memory
435737		bicsi	Keys (IOI21_keys)	C++17	100 / 100	1814 ms	114664 KiB

keys

#include <bits/stdc++.h>
 
using namespace std;
 
struct Solver {
  int n;
  vector<vector<int>> active;
  vector<multimap<int, int>> inactive;
  vector<set<int>> cols;
  vector<int> parent, df, link, bad;
 
  Solver(int n) : 
      n(n), active(n), inactive(n), cols(n),
      parent(n, -1), df(n, -1), link(n, -1), bad(n, 0) {}
 
  void AddEdge(int u, int v, int c) {
    if (cols[u].count(c))
      active[u].push_back(v);
    else 
      inactive[u].emplace(c, v);
  }
  void AddCol(int u, int c) {
    while (true) {
      auto it = inactive[u].find(c);
      if (it == inactive[u].end()) break;
      active[u].push_back(it->second);
      inactive[u].erase(it);
    }
    cols[u].insert(c);
  }
 
  void merge(int node, int anc) {
    while (true) {
      node = find(node);
      anc = find(anc);
      if (node == anc) return;
      int par = find(parent[node]);
      assert(par != node);
      link[node] = par;
      if (active[node].size() + cols[node].size() + inactive[node].size() > 
          active[par].size() + cols[par].size() + inactive[par].size()) {
        swap(active[node], active[par]);
        swap(cols[node], cols[par]);
        swap(inactive[node], inactive[par]);
        swap(bad[node], bad[par]);
      }
      for (auto x : cols[node])
        AddCol(par, x);
      for (auto x : active[node])
        active[par].push_back(x);
      for (auto [c, x] : inactive[node])
        AddEdge(par, x, c);
      bad[par] |= bad[node];
 
      inactive[node].clear();
      active[node].clear();
      cols[node].clear();
      bad[node] = 0;
    }
  }
 
  int find(int x) {
    if (link[x] == -1) return x;
    return link[x] = find(link[x]);
  }
 
  void dfs(int node, int par) {
    df[node] = 0;
    parent[node] = par;
    while (true) {
      node = find(node);
      if (active[node].empty()) break;
      int vec = active[node].back();
      active[node].pop_back();
      vec = find(vec);
      if (vec == node) continue;
      if (df[vec] == -1) {
        dfs(vec, node);
        if (find(vec) != find(node))
          bad[find(node)] = 1;
      } else if (df[vec] == 0) {
        merge(node, vec);
      } else {
        bad[find(node)] = 1;
      }
    }
    df[node] = 1;
  }
 
  vector<int> Solve() {
    for (int i = 0; i < n; ++i) 
      if (find(i) == i && df[i] == -1)
        dfs(i, -1);
    
    vector<int> ret(n, 0), sz(n, 0);
    int min_sz = 1e9;
    for (int i = 0; i < n; ++i) {
      if (bad[find(i)])
        continue;
      sz[find(i)] += 1;
    }
    for (int i = 0; i < n; ++i) {
      if (bad[find(i)])
        continue;
      min_sz = min(min_sz, sz[find(i)]);
    }
    for (int i = 0; i < n; ++i) {
      if (bad[find(i)])
        continue;
      ret[i] = (sz[find(i)] == min_sz);
    }
    return ret;
  }
 
};
 
vector<int> find_reachable(
    vector<int> r, vector<int> u, 
    vector<int> v, vector<int> c) {
	int n = r.size(), m = u.size();
  Solver S(n);
  for (int i = 0; i < n; ++i)
    S.AddCol(i, r[i]);
  for (int i = 0; i < m; ++i) {
    S.AddEdge(u[i], v[i], c[i]);
    S.AddEdge(v[i], u[i], c[i]);
  }
  return S.Solve();
}

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