Submission #1194738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194738		aykhn	Sphinx's Riddle (IOI24_sphinx)	C++20	28.50 / 100	115 ms	1172 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;
  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);
    // cout << comps[i] << ' ';
    if (!i || comps[i] == comps[i - 1] + 1) continue;
    int cnt = comps[i - 1] - comps[i] + 1;
    for (int k = 1, l = 0; k <= cnt; k++)
    {
      int r = i - 1;
      while (l < r)
      {
        int mid = (l + r) >> 1;
        vector<int> c(n, n);
        for (int l = 0; l <= mid; l++) c[l] = -1;
        c[i] = -1;
        int val = perform_experiment(c) - cntNs(c); 
        if (comps[mid] + 1 - k == val) r = mid;
        else l = mid + 1;
      }
      dsu.unite(i, l);
    }
  }
  // cout << '\n';
  vector<int> res(n, 0);
  for (int i = 0, idx = 0; i < n; i++)
  {
    if (dsu.get(i) != i) continue;
    res[i] = idx++;
  }
  for (int i = 0; i < n; i++) res[i] = res[dsu.get(i)];
  return res;
}

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