Submission #1194775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194775		aykhn	Sphinx's Riddle (IOI24_sphinx)	C++20	32 / 100	76 ms	1184 KiB

sphinx

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

using namespace std;

const int MXN = 250;

struct DSU
{
  vector<int> e;
  void init(int n)
  {
    e.assign(n, -1);
  }
  int get(int x)
  {
    if (e[x] < 0) return x;
    return e[x] = get(e[x]);
  }
  void unite(int x, int y)
  {
    x = get(x), y = get(y);
    if (x == y) return;
    if (e[x] > e[y]) swap(x, y);
    e[x] += e[y];
    e[y] = x;
  }
};

int n;
vector<int> adj[MXN];

void dfs(int a, vector<int> &used, vector<int> &col)
{
  used[a] = 1;
  for (int &v : adj[a])
  {
    if (used[v] || col[v] != n) continue;
    dfs(v, used, col);
  }
}

int cntNs(vector<int> &col)
{
  int res = 0;
  vector<int> used(n, 0);
  for (int i = 0; i < n; i++)
  {
    if (!used[i] && col[i] == n) res++, dfs(i, used, col);
  }
  return res;
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) 
{
  for (int i = 0; i < X.size(); i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
  n = N;
  for (int i = 0; i < n; i++) sort(adj[i].begin(), adj[i].end());
  DSU dsu;
  dsu.init(n);
  int comps[N];
  for (int i = 0; i < n; i++)
  {
    vector<int> q(n, 0);
    for (int j = 0; j <= i; j++) q[j] = -1;
    for (int j = i + 1; j < n; j++) q[j] = n;
    comps[i] = perform_experiment(q) - cntNs(q);
    if (!i || comps[i] == comps[i - 1] + 1) continue;
    int cnt = comps[i - 1] + 1 - comps[i];
    vector<int> used(n, 0);
    vector<int> o;
    for (int &j : adj[i])
    {
      if (j >= i) continue;
      if (used[dsu.get(j)]) continue;
      o.push_back(j);
      used[dsu.get(j)] = 1;
    }
    for (int k = 1, l = 0; k <= cnt; k++)
    {
      int r = (int)o.size() - 1;
      while (l < r)
      {
        int mid = (l + r) >> 1;
        vector<int> c(n, n);
        for (int j = 0; j <= o[mid]; j++) c[j] = -1;
        c[i] = -1;
        int val = comps[o[mid]] + 1 - (perform_experiment(c) - cntNs(c));
        if (val < k) l = mid + 1;
        else if (val >= k) r = mid;
      }
      dsu.unite(i, o[l]);
      l++;
    }
  }
  vector<int> res(n, 0);
  for (int i = 0; i < n; i++) res[i] = dsu.get(i);
  return res;
}

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