Submission #1176706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176706		Kanon	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	393 ms	1196 KiB

sphinx

#include <bits/stdc++.h>
#include "sphinx.h"

using namespace std;

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

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

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// generate random number between l, r : uniform_int_distribution<long long>(l, r)(rng)
// random shuffle : shuffle(.begin(), .end(), rng)
const int MAGIC_DEG = 32;

vector<int> find_colours(int n, vector<int> X, vector<int> Y) {
  vector<vector<int>> g(n);
  for (int i = 0; i < int(X.size()); i++) {
    int u = X[i], v = Y[i];
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> color(n, -1);
  vector<vector<int>> monochrome_graph(n);
  function<void(int, int)> add_color = [&](int v, int col) {
    if (color[v] != -1) {
      assert(color[v] == col);
      return;
    }
    color[v] = col;
    for (int u : monochrome_graph[v]) {
      add_color(u, col);
    }
  };
  auto add_monochrome = [&](int u, int v) {
    if (find(monochrome_graph[u].begin(), monochrome_graph[u].end(), v) != monochrome_graph[u].end()) return;
    monochrome_graph[u].push_back(v);
    monochrome_graph[v].push_back(u);
  };
  auto components_of_colored = [&](vector<int> coloring) {
    dsu d(n);
    int cnt = n;
    for (int v = 0; v < n; v++) {
      if (coloring[v] == -1) {
        cnt--;
        continue;
      }
      for (int u : g[v]) {
        if (coloring[u] != coloring[v]) continue;
        cnt -= d.unite(u, v);
      }
    }
    return cnt;
  };
  for (int v = 0; v < n; v++) {
    if (int(g[v].size()) > MAGIC_DEG) {
      vector<int> adj_nodes = g[v];
      vector<int> que_colors(n);
      iota(que_colors.begin(), que_colors.end(), 0);
      shuffle(que_colors.begin(), que_colors.end(), rng);
      while (que_colors.size() > adj_nodes.size()) {
        vector<int> try_color = vector<int>(que_colors.begin(), que_colors.begin() + adj_nodes.size());
        que_colors.erase(que_colors.begin(), que_colors.begin() + adj_nodes.size());
        vector<int> coloring(n, n);
        coloring[v] = -1;
        for (int i = 0; i < int(adj_nodes.size()); i++) {
          coloring[adj_nodes[i]] = try_color[i];
        }
        int comp_with_unique_v = components_of_colored(coloring) + 1;
        int comp_with_monochromable_v = perform_experiment(coloring);
        assert(comp_with_unique_v >= comp_with_monochromable_v);
        bool monochrome_reduce_comp = comp_with_unique_v > comp_with_monochromable_v;
        if (monochrome_reduce_comp) que_colors = try_color;
      }
      while (que_colors.size() > 1) {
        int sz = que_colors.size();
        vector<int> Left_colors = vector<int>(que_colors.begin(), que_colors.begin() + sz / 2);
        vector<int> coloring(n, n);
        coloring[v] = -1;
        for (int i = 0; i < int(Left_colors.size()); i++) {
          coloring[adj_nodes[i]] = Left_colors[i];
        }
        int comp_with_unique_v = components_of_colored(coloring) + 1;
        int comp_with_monochromable_v = perform_experiment(coloring);
        assert(comp_with_unique_v >= comp_with_monochromable_v);
        bool monochrome_reduce_comp = comp_with_unique_v > comp_with_monochromable_v;
        if (monochrome_reduce_comp) {
          que_colors = Left_colors;
        } else {
          que_colors = vector<int>(que_colors.begin() + sz / 2, que_colors.end());
        }
      }
      assert(que_colors.size() == 1);
      add_color(v, que_colors[0]);
    }
  }
  vector<int> process_order(n);
  iota(process_order.begin(), process_order.end(), 0);
  sort(process_order.begin(), process_order.end(), [&](int i, int j){return color[i] > color[j];});
  vector<bool> processed(n);
  dsu forest_spanning_monochrome(n);
  vector<int> current_roots;
  for (int v : process_order) {
    if (color[v] != -1) {
      vector<int> same_color_adj;
      for (int u : g[v]) {
        if (!processed[u]) continue;
        if (color[u] == color[v]) {
          same_color_adj.push_back(u);
        }
      }
      for (int u : same_color_adj) {
        int ru = forest_spanning_monochrome.get(u);
        auto it = find(current_roots.begin(), current_roots.end(), ru);
        if (it == current_roots.end()) continue;
        forest_spanning_monochrome.unite(ru, v);
        current_roots.erase(it);
        add_monochrome(u, v);
      }
      current_roots.push_back(v);
    } else {
      vector<int> adj_nodes_unique_color_root;
      for (int u : g[v]) {
        if (!processed[u]) continue;
        bool Unique = true;
        for (int w : g[v]) {
          if (w == u) break;
          if (!processed[w]) continue;
          if (forest_spanning_monochrome.get(w) == forest_spanning_monochrome.get(u)) {
            Unique = false;
            break;
          }
        }
        if (Unique) adj_nodes_unique_color_root.push_back(u);
      }

      vector<int> same_color_adj_nodes;
      function<void(vector<int>, int)> dfs = [&](vector<int> possible_same_color_adj_nodes, int total_same_color) {
        if (total_same_color == 0) return;
        int sz = possible_same_color_adj_nodes.size();
        if (total_same_color == sz) {
          for (int nd : possible_same_color_adj_nodes) same_color_adj_nodes.push_back(nd);
          return;
        }
        vector<int> coloring(n, n);
        coloring[v] = -1;
        for (int i = 0; i < sz / 2; i++) {
          coloring[possible_same_color_adj_nodes[i]] = -1;
        }
        int Left_connected_nodes = components_of_colored(coloring) + sz / 2 + 1 - perform_experiment(coloring);
        int Right_connected_nodes = total_same_color - Left_connected_nodes;
        dfs(vector<int>(possible_same_color_adj_nodes.begin(), possible_same_color_adj_nodes.begin() + sz / 2), Left_connected_nodes);
        dfs(vector<int>(possible_same_color_adj_nodes.begin() + sz / 2, possible_same_color_adj_nodes.end()), Right_connected_nodes);
      };
      vector<int> coloring(n, n);
      coloring[v] = -1;
      for (int i : adj_nodes_unique_color_root) coloring[i] = -1;
      int total_same_color = components_of_colored(coloring) + adj_nodes_unique_color_root.size() + 1 - perform_experiment(coloring);
      dfs(adj_nodes_unique_color_root, total_same_color);
      for (int nd : same_color_adj_nodes) {
        add_monochrome(nd, v);
        nd = forest_spanning_monochrome.get(nd);
        auto it = find(current_roots.begin(), current_roots.end(), nd);
        if (it == current_roots.end()) continue;
        current_roots.erase(it);
        forest_spanning_monochrome.unite(nd, v);
      }
      for (int nd : same_color_adj_nodes) {
        if (color[nd] != -1) {
          assert(color[v] == -1 || color[v] == color[nd]);
          add_color(v, color[nd]);
        }
      }
      current_roots.push_back(v);
    }
    processed[v] = true;
  }
  vector<int> choose(n);
  while (true) {
    bool change = false;
    for (int v = 0; v < n; v++) {
      int bal = 0;
      for (int u : g[v]) {
        if (choose[u] == (choose[v] ^ 1)) {
          bal += 1;
        } else {
          bal -= 1;
        }
      }
      if (bal < 0) {
        choose[v] ^= 1;
        change = true;
      }
    }
    if (!change) break;
  }
  vector<vector<int>> Total_adj_batch(2);
  for (int v = 0; v < n; v++) Total_adj_batch[choose[v]].push_back(v);
  for (int rot = 0; rot < 2; rot++) {
    vector<int> Seekers;
    vector<int> Helpers = Total_adj_batch[rot ^ 1];
    for (int v : Total_adj_batch[rot]) {
      if (color[v] == -1 && forest_spanning_monochrome.get(v) == v) Seekers.push_back(v);
    }
    if (Seekers.empty()) continue;
    for (int col = 0; col < n; col++) {
      if (Seekers.empty()) break;
      vector<int> colled;
      function<void(vector<int>, int, int)> dfs = [&](vector<int> Candidates, int col_spanning_edges, int so_far) {
        if (col_spanning_edges == 0) return;
        if (Candidates.size() == 1) {
          assert(so_far <= 7);
          colled.push_back(Candidates[0]);
          return;
        }
        int sz = Candidates.size();
        vector<int> coloring(n, n);
        for (int v : Helpers) coloring[v] = col;
        for (int i = 0; i < sz / 2; i++) coloring[Candidates[i]] = -1;
        int Left_col_spanning_edges = components_of_colored(coloring) + sz / 2 - perform_experiment(coloring);
        bool is_right_needed = col_spanning_edges > Left_col_spanning_edges;
        int Right_col_spanning_edges = 0;
        if (is_right_needed) {
          if (Left_col_spanning_edges > 0) {
            for (int i = 0; i < sz / 2; i++) coloring[Candidates[i]] = n;
            for (int i = sz / 2; i < sz; i++) coloring[Candidates[i]] = -1;
            Right_col_spanning_edges = components_of_colored(coloring) + sz - sz / 2 - perform_experiment(coloring);
            assert(Right_col_spanning_edges > 0);
          } else {
            Right_col_spanning_edges = col_spanning_edges;
          }
        }
        assert(Left_col_spanning_edges > 0 || Right_col_spanning_edges > 0);
        dfs(vector<int>(Candidates.begin(), Candidates.begin() + sz / 2), Left_col_spanning_edges, so_far + 1);
        dfs(vector<int>(Candidates.begin() + sz / 2, Candidates.end()), Right_col_spanning_edges, so_far + 1);
      };
      vector<int> coloring(n, n);
      for (int v : Seekers) coloring[v] = -1;
      for (int v : Helpers) coloring[v] = col;
      int col_spanning_edges = components_of_colored(coloring) + Seekers.size() - perform_experiment(coloring);
      dfs(Seekers, col_spanning_edges, 0);
      for (int v : colled) {
        add_color(v, col);
        Seekers.erase(find(Seekers.begin(), Seekers.end(), v));
      }
    }
    assert(Seekers.empty());
  }
  assert(count(color.begin(), color.end(), -1) == 0);
  return color;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 33 / 33
• Subtask 4: 21 / 21
• Subtask 5: 36 / 36