Submission #1029665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029665		NeroZein	Keys (IOI21_keys)	C++17	0 / 100	31 ms	70788 KiB

keys

#include <bits/stdc++.h>
using namespace std; 

const int N = 3e5 + 5; 

int n, m;
int vis[N];
int nxt[N];
vector<int> city_key;
vector<pair<int, int>> g[N];

int p2[N], sz2[N];

bool valid[N];
int p[N], sz[N];
vector<int> nodes[N];
set<int> active_keys[N];
set<int> owned_colors[N];
set<int> needed_colors[N];
set<pair<int, int>> inactive_key[N];

int get2(int v) {
  return p2[v] = (p2[v] == v ? v : get2(p2[v]));
}

void unite2(int u, int v) {
  u = get2(u); 
  v = get2(v);
  if (u == v) {
    return;
  }
  if (sz2[u] > sz2[v]) swap(u, v);
  sz2[v] += sz2[u];
  p2[u] = v;
}

void init_dsu2() {
  for (int i = 0; i < n; ++i) {
    p2[i] = i;
    sz[i] = 1; 
  }
  for (int i = 0; i < n; ++i) {
    unite2(i, nxt[i]);
  }
}

void init_dsu() {
  for (int i = 0; i < n; ++i) {
    p[i] = i;
    sz[i] = 1; 
    nodes[i].push_back(i);
    owned_colors[i].insert(city_key[i]);
    for (auto [u, edge_key] : g[i]) {
      if (edge_key == city_key[i] && u != nxt[i]) {
        active_keys[i].insert(u);
      } else if (edge_key != city_key[i]) {
        needed_colors[i].insert(edge_key);
        inactive_key[i].insert({edge_key, u});
      }
    }
  }
}

int get(int v) {
  return p[v] = (p[v] == v ? v : get(p[v]));
}

void unite(int u, int v) {
  u = get(u);
  v = get(v);
  if (u == v) {
    return; 
  }
  if (sz[u] > sz[v]) {
    swap(u, v);
  }
  sz[v] += sz[u];
  p[u] = v; 
  for (int w : nodes[u]) {
    nodes[v].push_back(w); 
  }
  for (auto w : active_keys[u]) {
    active_keys[v].insert(w); 
  }
  for (auto c : owned_colors[u]) {
    if (owned_colors[v].count(c)) {
      continue; 
    }
    while (true) {
      auto it = inactive_key[v].lower_bound({c, 0});
      if (it == inactive_key[v].end() || it->first != c) {
        break; 
      }
      active_keys[v].insert(it->second);
      inactive_key[v].erase(it); 
    }
    owned_colors[v].insert(c);
  }
  for (auto c : needed_colors[u]) {
    if (!owned_colors[v].count(c)) {
      needed_colors[v].insert(c);
      continue; 
    }
    while (true) {
      auto it = inactive_key[u].lower_bound({c, 0});
      if (it == inactive_key[u].end() || it->first != c) {
        break;
      }
      active_keys[v].insert(it->second);
      inactive_key[u].erase(it); 
    }
  }
  for (auto [c, w] : inactive_key[u]) {
    inactive_key[v].insert({c, w}); 
  }
  valid[v] = true;
}

vector<int> find_reachable(vector<int> r, vector<int> u_, vector<int> v_, vector<int> c) {
  city_key = r;
  n = (int) city_key.size(); 
  m = (int) u_.size();
  for (int i = 0; i < m; ++i) {
    g[u_[i]].push_back({v_[i], c[i]});
    g[v_[i]].push_back({u_[i], c[i]});
  }
  vector<int> ans(n);
  bool ok = true;
  for (int v = 0; v < n; ++v) {
    bool f = false;
    for (auto [u, edge_key] : g[v]) {
      if (edge_key == city_key[v]) {
        nxt[v] = u; 
        f = true; 
      }
    }
    if (!f) {
      ok = false; 
      ans[v] = 1; 
    }
  }
  if (!ok) {
    return ans;    
  }
  init_dsu2();
  init_dsu();
  vector<int> stk; 
  function<void(int)> dfs = [&](int v) {
    if (vis[v] == 2) {
      return;
    }
    if (vis[v] == 1) {
      assert(get(v) == v); 
      valid[v] = true;
      while (stk.back() != v) {
        int top = stk.back();
        stk.pop_back();
        unite(top, v);
      }
      return; 
    }
    vis[v] = 1; 
    stk.push_back(v); 
    dfs(nxt[v]); 
    if (!stk.empty() && stk.back() == v) {
      stk.pop_back();      
    }
    vis[v] = 2; 
  };
  for (int i = 0; i < n; ++i) {
    dfs(i);
  }
  //cout << "DEBUG: " << endl;
  //for (int i = 0; i < n; ++i) {
    //cout << "nxt: " << i << ' ' << nxt[i] << ' ' << get(i) << '\n'; 
  //}
  //cout << "DEBUG: " << endl;
  //for (int i = 0; i < n; ++i) {
    //if (get(i) != i || valid[p[i]] != 1) {
      //continue; 
    //}
    //cout << "Cycle: " << i << ' ' << get(i) << ' ' << valid[p[i]] << '\n'; 
  //}
  set<int> roots;
  for (int i = 0; i < n; ++i) {
    if (get(i) == i && valid[i] == true) {
      roots.insert(i); 
    }
  }
  while (!roots.empty()) {
    int root = *roots.begin();
    roots.erase(root); 
    assert(get(root) == root);
    vector<int> toErase; 
    for (auto u : active_keys[root]) {//make sure this iterates over everything.
      if (get2(u) == get2(root)) {
        int x = u; 
        while (get(x) != get(root)) {
          unite(x, root);
          x = nxt[x]; 
        }
        toErase.push_back(u);
      } else {
        //roots.insert(get(u));//nothing needs to be inserted???
        unite2(u, root); 
        valid[root] = false;
        nxt[root] = get(u);
        break; 
      }
    }
  }
  int mn = n; 
  for (int i = 0; i < n; ++i) {
    if (get(i) != i || !valid[i]) {
      continue; 
    }
    mn = min(mn, sz[i]);
  }
  for (int i = 0; i < n; ++i) {
    if (sz[get(i)] == mn) {
      ans[i] = 1;
    }
  }
  return ans; 
}

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