제출 #1194779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194779		aykhn	Sphinx's Riddle (IOI24_sphinx)	C++20	28.50 / 100	83 ms	1208 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;
}

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]);
  for (int i = 0; i < n; i++) sort(adj[i].begin(), adj[i].end());
  DSU dsu;
  dsu.init(n);
  int comps[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;
    comps[i] = getcomps(q);
    if (!i || comps[i] == comps[i - 1] + 1) 
    {
      cc.push_back({i});
      continue;
    }
    cc.push_back({i});
    vector<int> del(cc.size(), 0);
    int cnt = comps[i - 1] + 1 - comps[i];
    for (int k = 1, l = 0; k <= cnt; k++)
    {
      int r = (int)cc.size() - 1;
      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> res(n, 0);
  for (int i = 0; i < cc.size(); i++) for (int &j : cc[i]) res[j] = 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