Submission #1204051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204051		abczz	Sphinx's Riddle (IOI24_sphinx)	C++20	In queue	0 ms	0 KiB

sphinx

#include "sphinx.h"
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

vector <ll> adj[250], V[250];
vector <int> E;
bool visited[250], B[250];
ll n, deg[250], s, mn, k, G[250], mex[250];
vector <int> F;

void dfs(ll u) {
  if ((ll)adj[u].size() >= k) return;
  for (int i=0; i<n; ++i) mex[i] = -1;
  for (auto v : adj[u]) {
    if (G[v] != -1) mex[G[v]] = 1;
  }
  for (int i=0; i<n; ++i) {
    if (mex[i]  == -1) {
      G[u] = i;
      break;
    }
  }
  for (auto v : adj[u]) {
    if (G[v] == -1) dfs(v);
  }
}

void color(ll u) {
  for (int i=0; i<n; ++i) E[i] = u;
}

void dfs2(ll u) {
  visited[u] = 1;
  if (E[u] == -1) return;
  for (auto v : adj[u]) {
    if (!visited[v] && E[u] == E[v]) dfs2(v);
  }
}
ll count() {
  ll tot = 0;
  for (int i=0; i<n; ++i) visited[i] = 0;
  for (int i=0; i<n; ++i) {
    if (!visited[i]) dfs2(i), ++tot;
  }
  return tot;
}

std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
  for (int i=0; i<N; ++i) adj[i].clear(), V[i].clear(), deg[i] = B[i] = 0, G[i] = -1;
  n = N;
  F.resize(n);
  E.clear();
  for (int i=0; i<n; ++i) E.push_back(0);
  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) {
    ++deg[(ll)adj[i].size()-1];
  }
  s = 0, mn = 1e18, k = -1;
  for (ll i=0; i<n; ++i) {
    s += deg[i];
    ll cur = n * (i+2) + (n-s) * n / (i+2);
    if (cur < mn) mn = cur, k = i+2;
  }
  for (int i=0; i<n; ++i) {
    if ((ll)adj[i].size() < k) {
      if (G[i] == -1) dfs(i);
      V[G[i]].push_back(i);
    }
    else {
      ll l = -1, r = -1, mid;
      for (int c=0; c+(ll)adj[i].size()<n; c+=(ll)adj[i].size()) {
        color(n);
        ll x = 0;
        E[i] = -1;
        for (int j=c; j<min(n, c+(ll)adj[i].size()); ++j) {
          E[adj[i][x++]] = j;
        }
        ll res = perform_experiment(E);
        if (res != count()) {
          l = c, r = min(n, c+(ll)adj[i].size())-1;
          break;
        }
      }
      if (l == -1) l = (ll)(n/(ll)adj[i].size()) * (ll)adj[i].size(), r = n-1;
      while (l < r) {
        mid = (l+r)/2;
        color(n);
        ll x = 0;
        E[i] = -1;
        for (int j=l; j<=mid; ++j) E[adj[i][x++]] = j;
        ll res = perform_experiment(E);
        if (res != count()) r = mid;
        else l = mid+1;
      }
      F[i] = l;
    }
  }
  for (int i=0; i<n; ++i) {
    if (V[i].empty()) continue;
    for (int j=0; j<n; ++j) {
      while (true) {
        color(j);
        for (auto u : V[i]) E[u] = (B[u] ? n : -1);
        ll res = perform_experiment(E);
        if (res == count()) break;
        ll l = 0, r = V[i].size()-1, mid;
        while (l < r) {
          mid = (l+r)/2;
          color(j);
          for (int x=l; x<=mid; ++x) E[V[i][x]] = (B[V[i][x]] ? n : -1);
          res = perform_experiment(E);
          if (res != count()) r = mid;
          else l = mid+1;
        }
        F[V[i][l]] = j;
        B[V[i][l]] = 1;
      }
    }
  }
  return F;
}