Submission #1279299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279299		avighna	Sphinx's Riddle (IOI24_sphinx)	C++20	18 / 100	1539 ms	1316 KiB

sphinx

#include <bits/stdc++.h>

int perform_experiment(std::vector<int> E);

int n;
std::vector<std::vector<int>> adj;

int query(const std::vector<int> &c) {
  if (std::find(c.begin(), c.end(), -1) != c.end()) {
    return perform_experiment(c);
  }
  int ans = 0;
  std::queue<int> q;
  std::vector<bool> vis(n);
  for (int i = 0; i < n; ++i) {
    if (vis[i]) {
      continue;
    }
    ans++;
    q.push(i);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      vis[u] = true;
      for (int &i : adj[u]) {
        if (!vis[i] and c[u] == c[i]) {
          q.push(i);
        }
      }
    }
  }
  return ans;
}

class dsu {
private:
  int n;
  std::vector<int> par, size;
  std::vector<std::vector<int>> comp_m;

public:
  dsu(int n) : n(n), par(n), size(n, 1), comp_m(n) {
    std::iota(par.begin(), par.end(), 0);
    for (int i = 0; i < n; ++i) {
      comp_m[i].push_back(i);
    }
  }

  int root(int u) { return u == par[u] ? u : par[u] = root(par[u]); }

  void merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) {
      return;
    }
    if (size[u] < size[v]) {
      std::swap(u, v);
    }
    for (int &i : comp_m[v]) {
      comp_m[u].push_back(i);
    }
    par[v] = u;
    size[u] += size[v];
  }

  const std::vector<int> &comp(int u) { return comp_m[root(u)]; }
};

std::vector<int> find_colours(int N, std::vector<int> x, std::vector<int> y) {
  n = N;
  adj.resize(n);
  for (int i = 0; i < x.size(); ++i) {
    adj[x[i]].push_back(y[i]);
    adj[y[i]].push_back(x[i]);
  }

  std::vector<bool> vis(n);
  std::vector<int> ord;
  auto dfs = [&](auto &&self, int u) {
    if (vis[u]) {
      return;
    }
    vis[u] = true;
    for (int &i : adj[u]) {
      self(self, i);
    }
    ord.push_back(u);
  };
  dfs(dfs, 0);
  std::reverse(ord.begin(), ord.end());

  dsu dsu(n);
  vis.assign(n, false);
  vis[0] = true;
  for (int i = 1; i < n; ++i) {
    int u = ord[i];
    vis[u] = true;
    std::vector<bool> seen(n);
    std::vector<int> nodes;
    for (int i : adj[u]) {
      i = dsu.root(i);
      if (!vis[i] or seen[i]) {
        continue;
      }
      seen[i] = true;
      nodes.push_back(i);
    }
    auto has = [&](int till) {
      std::vector<int> q(n, n);
      for (int i = 0; i <= till; ++i) {
        for (int u : dsu.comp(nodes[i])) {
          q[u] = dsu.root(nodes[i]);
        }
      }
      q[u] = n + 1;
      int bef = query(q);

      for (int i = 0; i <= till; ++i) {
        for (int u : dsu.comp(nodes[i])) {
          q[u] = -1;
        }
      }
      q[u] = -1;
      int aft = query(q);
      return bef != aft;
    };
    int fr;
    if (!has(nodes.size() - 1)) {
      fr = nodes.size();
    } else {
      fr = *std::ranges::partition_point(std::views::iota(0, int(nodes.size())), [&](int i) {
        return !has(i);
      });
    }
    if (fr != nodes.size()) {
      dsu.merge(u, nodes[fr]);
    }
  }

  std::vector<int> ans(n);
  for (int i = 0; i < n; ++i) {
    ans[i] = dsu.root(i);
  }
  return ans;
}

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