Submission #497775

#	Time	Username	Problem	Language	Result	Execution time	Memory
497775		MilosMilutinovic	열쇠 (IOI21_keys)	C++17	0 / 100	1 ms	204 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<vector<int>> ch(n);
  vector<int> id(n);
  for (int i = 0; i < n; i++) {
    //comp[i].init(i, c[i]);
    ch[i] = {i};
    id[i] = i;
  }
  vector<int> ans(n, 1e9);
  vector<int> par(n);
  vector<int> comp(n);
  for (int i = 0; i < n; i++) {
    par[i] = i;
    id[i] = i;
    comp[i] = i;
  }
  // comp[u] - spec node of component with node u
  function<int(int)> who = [&](int u) {
    return par[u] == u ? u : par[u] = who(par[u]);
  };
  function<int(int)> root = [&](int u) {
    //return comp[u] == u ? u : comp[u] = root(comp[u]);
    return comp[id[u]];
  };
  function<void(int, int)> Merge = [&](int u, int v) {
    int my_u = u;
    int my_v = v;
    //u = who(u);
    //v = who(v);
    //if (ch[u].size() > ch[v].size()) swap(u, v);
    if (ch[u].size() <= ch[v].size()) {
      for (int i : ch[u]) {
        ch[v].push_back(i);
        id[i] = id[v];
      }
      ch[u].clear();
      //par[u] = v;
      comp[id[v]] = my_v;
    } else {
      for (int i : ch[v]) {
        ch[u].push_back(i);
        id[i] = id[u];
      }
      ch[v].clear();
      comp[id[u]] = v;
    }
  };
  for (int foo = 0; foo < 25; foo++) {
    vector<bool> mrg(n, false);
    vector<bool> was(n, false);
    vector<vector<int>> mp(n);
    vector<bool> have(n, false);
    vector<int> vec;
    for (int i = 0; i < n; i++) {
      if (mrg[root(i)] || ans[root(i)] != 1e9) {
        continue;
      }
      int other = -1;
      vector<int> vis;
      vec.clear();
      function<void(int)> Dfs = [&](int u) {
        if (root(u) != root(i)) {
          other = u;
          return;
        }
        if (other != -1 || was[u]) {
          return;
        }
        vis.push_back(u);
        was[u] = true;
        have[c[u]] = true;
        vec.push_back(c[u]);
        for (auto x : mp[c[u]]) {
          Dfs(x);
          if (other != -1) {
            return;
          }
        }
        mp[c[u]].clear();
        for (auto e : g[u]) {
          if (have[e.second]) {
            Dfs(e.first);
            if (other != -1) {
              return;
            }
          } else {
            mp[e.second].push_back(e.first);
            vec.push_back(e.second);
          }
        }
      };
      Dfs(root(i));
      for (int pp : vec) {
        mp[pp].clear();
        have[pp] = false;
      }
      if (other == -1) {
        for (int u : vis) {
          ans[u] = vis.size();
        }
      } else {
        Merge(root(i), root(other));
        mrg[root(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;
}

Compilation message (stderr)

keys.cpp: In lambda function:
keys.cpp:46:9: warning: unused variable 'my_u' [-Wunused-variable]
   46 |     int my_u = u;
      |         ^~~~

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