Submission #1278426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278426		avighna	Sphinx's Riddle (IOI24_sphinx)	C++20	10 / 100	299 ms	1160 KiB

sphinx

#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>

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

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

public:
  dsu(int n) : n(n), par(n) { std::iota(par.begin(), par.end(), 0); }

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

  bool merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) {
      return false;
    }
    par[v] = u;
    return true;
  }
};

std::vector<int> find_colours(int n, std::vector<int> x, std::vector<int> y) {
  const int m = x.size();
  auto comps = [&](int u, int v) {
    dsu dsu(n);
    int ans = n - 2;
    for (int i = 0; i < m; ++i) {
      if (x[i] != u and x[i] != v and y[i] != v and y[i] != u) {
        ans -= dsu.merge(x[i], y[i]);
      }
    }
    return ans;
  };
  std::vector<int> ans(n);
  std::vector<bool> done(n);
  for (int i = 0; i < m; ++i) {
    x.push_back(y[i]);
    y.push_back(x[i]);
  }
  for (int i = 0; i < 2 * m; ++i) {
    int u = x[i], v = y[i];
    if (done[u]) {
      std::swap(u, v);
    }
    if (done[u]) {
      continue;
    }
    for (int c = 0; c < n; ++c) {
      if (done[u]) {
        break;
      }
      std::vector<int> q(n, n);
      q[u] = -1;
      q[v] = c;
      if (perform_experiment(q) - comps(u, v) == 1) {
        ans[u] = c;
        done[u] = true;
      }
    }
    assert(done[u]);
  }
  return ans;
}

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