Submission #1020735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020735		NeroZein	Keys (IOI21_keys)	C++17	9 / 100	3104 ms	928184 KiB

keys

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

vector<int> find_reachable(vector<int> city_key, vector<int> u_, vector<int> v_, vector<int> c) {
  int n = (int) city_key.size();
  int m = (int) u_.size();
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    int u = u_[i], v = v_[i], edge_key = c[i];
    g[u].emplace_back(v, edge_key);
    g[v].emplace_back(u, edge_key);
  } 
  
  int idd = n; 
  set<pair<int, int>> edges;
  vector<vector<int>> t(n), rt(n);
  auto add_edge = [&](int u, int v) {
    if (!edges.count({u, v})) {
      t[u].push_back(v);
      rt[v].push_back(u);
      edges.insert({u, v});       
    }
  };
  for (int current_key = 0; current_key < 30; ++current_key) {//build graph t, rt
    vector<bool> vis(n); 
    function<void(int, int)> dfs = [&](int v, int p) {
      vis[v] = true; 
      add_edge(p, v);
      if (city_key[v] == current_key) {
        add_edge(v, p);
      }
      for (auto [u, edge_key] : g[v]) {
        if (edge_key == current_key && !vis[u]) {
          dfs(u, p); 
        }
      }
    };
    for (int v = 0; v < n; ++v) {
      if (!vis[v]) {
        t.push_back({});
        rt.push_back({});
        dfs(v, idd++);
      }
    }
  }
  
  vector<int> stk, vis(idd);
  function<void(int)> dfs = [&](int v) {
    vis[v] = true;
    for (int u : t[v]) {
      if (!vis[u]) {
        dfs(u);
      }
    }
    stk.push_back(v); 
  };
  for (int i = 0; i < idd; ++i) {//find dfs order
    if (!vis[i]) {
      dfs(i);
    }
  }
  
  vector<int> sz(idd); 
  vector<vector<int>> sccg(idd); 
  function<void(int, int)> dfs2 = [&](int v, int comp) {//build sccg & find sizes
    vis[v] = comp;
    sz[comp] += v < n;
    for (int u : rt[v]) {
      if (vis[u] == -1) {
        dfs2(u, comp);
      } else if (vis[u] != vis[v]) {
        //if (u < n && v < n) {
          //cout << "u, v, vis[u], vis[v]: " << u << ' ' << v << ' ' << vis[u] << ' ' << vis[v] << endl;           
        //}
        sccg[vis[u]].push_back(vis[v]); 
      }
    }
  };
  assert((int) stk.size() == idd);
  int comp = 0;
  for (int i = 0; i < idd; ++i) {
    vis[i] = -1; 
  }
  for (int i = idd - 1; i >= 0; --i) {
    int v = stk[i]; 
    if (vis[v] == -1) {
      dfs2(v, comp++); 
    }
  }
  vector<bool> vis2(comp);
  function<void(int)> dfs3 = [&](int v) {//get subtree sizes
    vis2[v] = true;
    for (int u : sccg[v]) {
      if (!vis2[u]) {
        dfs3(u);
      }
      sz[v] += sz[u]; 
    }
  };
  for (int i = 0; i < comp; ++i) {
    if (!vis2[i]) {
      sort(sccg[i].begin(), sccg[i].end());
      sccg[i].resize(unique(sccg[i].begin(), sccg[i].end()) - sccg[i].begin());
      dfs3(i); 
    }
  }
  
  int mn = n; 
  for (int i = 0; i < n; ++i) {
    mn = min(mn, sz[vis[i]]);
    //cout << "i, vis[i] " << i << ' ' << vis[i] << ' ' << sz[vis[i]] << '\n';
  }
  vector<int> ans(n);
  for (int i = 0; i < n; ++i) {
    if (sz[vis[i]] == mn) {
      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