Submission #1195334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195334		aykhn	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	290 ms	1608 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], g[MXN];
int bic[MXN], u[MXN];

void bicol(int a)
{
  u[a] = 1;
  for (int &v : g[a])
  {
    if (u[v]) continue;
    bic[v] = bic[a] ^ 1;
    bicol(v);
  }
}

void dfs(int a, vector<int> &used, vector<int> &col)
{
  used[a] = 1;
  for (int &v : adj[a])
  {
    if (used[v] || col[v] == -1) 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] != -1) res++, dfs(i, used, col);
  }
  return res;
}
int getcomps(vector<int> &col)
{
  return perform_experiment(col) - cntNs(col);
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) 
{
  n = N;
  for (int i = 0; i < X.size(); i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
  DSU dsu;
  dsu.init(n);
  vector<vector<int>> cc;
  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;
    int cur = getcomps(q);
    cc.push_back({i});
    if (!i || cur == cc.size()) continue;
    vector<int> del(cc.size(), 0);
    int cnt = (int)cc.size() - cur;
    for (int k = 1, l = 0; k <= cnt; k++)
    {
      int r = (int)cc.size() - 2;
      while (l < r)
      {
        int mid = (l + r) >> 1;
        vector<int> q(n, n);
        for (int i = l; i <= mid; i++)
        {
          for (int &j : cc[i]) q[j] = -1;
        }
        q[i] = -1;
        if (getcomps(q) <= mid - l + 1) r = mid;
        else l = mid + 1;
      }
      for (int &j : cc[l]) cc.back().push_back(j);
      del[l] = 1;
      l++;
    }
    for (int i = (int)cc.size() - 1; i >= 0; i--) if (del[i]) cc.erase(cc.begin() + i);
  }
  vector<int> comp(n, 0);
  for (int i = 0; i < cc.size(); i++) for (int &j : cc[i]) comp[j] = i;
  for (int i = 0; i < X.size(); i++)
  {
    if (comp[X[i]] != comp[Y[i]]) g[comp[X[i]]].push_back(comp[Y[i]]), g[comp[Y[i]]].push_back(comp[X[i]]);
  }
  for (int i = 0; i < cc.size(); i++)
  {
    if (!u[i]) bicol(i);
  }
  vector<int> real(cc.size());
  for (int val = 0; val < n; val++)
  {
    for (int p = 0; p < 2; p++)
    {
      vector<int> q(n, val);
      int cnt = 0;
      for (int i = 0; i < cc.size(); i++)
      {
        if (bic[i] == p) q[cc[i][0]] = -1, cnt++;
      }
      int cur = perform_experiment(q);
      int valcomps = cntNs(q);
      // cur = valcomps + cnt
      for (int l = 0; cur < valcomps + cnt;)
      {
        int r = (int)cc.size() - 1;
        while (l < r)
        {
          int mid = (l + r) >> 1;
          vector<int> q(n, val);
          int cnt = 0;
          for (int i = l; i <= mid; i++)
          {
            if (bic[i] == p) q[cc[i][0]] = -1, cnt++;
          }
          if (getcomps(q) == cnt) l = mid + 1;
          else r = mid;
        }
        real[l] = val;
        cnt--;
        q[cc[l][0]] = val;
        valcomps = cntNs(q);
        l++;
      }
    }
  }
  vector<int> res(n, 0);
  for (int i = 0; i < cc.size(); i++) for (int &j : cc[i]) res[j] = real[i];
  return res;
}

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