Submission #486916

#	Time	Username	Problem	Language	Result	Execution time	Memory
486916		MilosMilutinovic	Keys (IOI21_keys)	C++17	37 / 100	3085 ms	80428 KiB

keys

#include <bits/stdc++.h>

using namespace std;

/*struct component {
  int root;
  set<int> keys;
  void init(int u, int c) {
    root = u;
    keys.insert(c);
  }
};*/

vector<int> find_reachable(vector<int> c, vector<int> u, vector<int> v, vector<int> r) {
  int n = c.size();
  int m = u.size();
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    g[u[i]].emplace_back(v[i], r[i]);
    g[v[i]].emplace_back(u[i], r[i]);
  }
  vector<set<int>> keys(n);
  vector<vector<int>> ch(n);
  vector<int> id(n);
  for (int i = 0; i < n; i++) {
    //comp[i].init(i, c[i]);
    keys[i].insert(c[i]);
    ch[i] = {i};
    id[i] = i;
  }
  function<void(int, int)> Merge = [&](int u, int v) {
    for (int i : keys[u]) {
      keys[v].insert(i);
    }
    keys[u].clear();
    for (int i : ch[u]) {
      ch[v].push_back(i);
      id[i] = v;
    }
    ch[u].clear();
  };
  vector<int> ans(n, 1e9);
  for (int foo = 0; foo < 30; foo++) {
    vector<bool> mrg(n, false);
    vector<bool> was(n, false);
    for (int i = 0; i < n; i++) {
      if (mrg[id[i]] || ans[id[i]] != 1e9) {
        continue;
      }
      int other = -1;
      set<int> s;
      vector<int> vis;
      map<int, vector<int>> mp;
      function<void(int)> Dfs = [&](int u) {
        if (id[u] != id[i]) {
          other = u;
          return;
        }
        if (other != -1 || was[u]) {
          return;
        }
        vis.push_back(u);
        was[u] = true;
        s.insert(c[u]);
        for (auto x : mp[c[u]]) {
          Dfs(x);
          if (other != -1) {
            return;
          }
        }
        mp[c[u]].clear();
        for (auto e : g[u]) {
          if (s.find(e.second) != s.end()) {
            Dfs(e.first);
            if (other != -1) {
              return;
            }
          } else {
            mp[e.second].push_back(e.first);
          }
        }
      };
      Dfs(id[i]);
      if (other == -1) {
        for (int u : vis) {
          ans[u] = vis.size();
        }
      } else {
        Merge(id[i], id[other]);
        mrg[id[i]] = true;
        //mrg[id[other]] = true;
      }
    }
  }
  int mn = *min_element(ans.begin(), ans.end());
  for (int i = 0; i < n; i++) {
    ans[i] = (ans[i] == mn ? 1 : 0);
  }
  return ans;
}

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