Submission #1210067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210067		trimkus	Sphinx's Riddle (IOI24_sphinx)	C++20	28.50 / 100	1283 ms	2162688 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> E;
int N;
const int MAXN = 250;
int p[MAXN];
bool vis[MAXN];
vector<int> adj[MAXN];
int get(int x) {
  return (p[x] < 0 ? x : p[x] = get(p[x]));
}
int color(int x) {
  return (E[x] >= 0 ? E[x] + N : get(x));
}



int expected() {
  int cnt = 0;
  auto dfs = [&](auto& dfs, int i) -> void {
    vis[i] = true;
    for (auto& u : adj[i]) {
      if (vis[u]) continue;
      if (color(i) != color(u)) continue;
      dfs(dfs, u);
    }
  };
  for (int i = 0; i < N; ++i) vis[i] = false;
  for (int i = 0; i < N; ++i) {
    if (!vis[i]) {
      cnt++;
      dfs(dfs, i);
    }
  }
  return cnt;
}

std::vector<int> find_colours(int _N, std::vector<int> X, std::vector<int> Y) {
  N = _N;
  E = vector<int>(N);
  vector<int> F(N, -1);
  vector<bool> online(N);
  for (int i = 0; i < (int)X.size(); ++i) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < N; ++i) {
    p[i] = -1;
  }
  for (int i = 1; i < N; ++i) {
    while (true) {
      for (int j = 0; j <= i; ++j) E[j] = -1;
      for (int j = i + 1; j < N; ++j) E[j] = N;
      if (expected() == perform_experiment(E)) {
        break;
      }
      // cerr << "NOW CHECKING: [0, " << i - 1 << "], with vertice at: " << i << endl;
      // must be at least one vertice same color as i
      set<int> st;
      vector<int> pool;
      for (int j = 0; j < i; ++j) {
        if (get(j) != i) {
          st.insert(j);
        }
      }
      while (st.size()) {
        pool.push_back(*begin(st));
        st.erase(begin(st));
      }
      // cerr << "POOL = ";
      // for (auto& u : pool) {
      //   cerr << u << " ";
      // }
      // cerr << "\n";
      int left = 0, right = (int)pool.size() - 1;
      while (left < right) {
        // cerr << "[" << left << ", " << right << "]\n";
        int mid = (left + right) / 2;
        for (int j = 0; j < N; ++j) {
          online[j] = false;
        }
        for (int j = 0; j <= mid; ++j) {
          online[pool[j]] = 1;
        }
        for (int j = 0; j < i; ++j) {
          if (online[get(j)]) {
            E[j] = -1;
          } else {
            E[j] = N;
          }
        }
        E[i] = -1;
        // repetitive?
        for (int j = i + 1; j < N; ++j) {
          E[j] = N;
        }
        if (expected() == perform_experiment(E)) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      p[get(right)] = i;
    }
  }
  map<int, int> mp;
  for (int i = 0; i < N; ++i) {
    if (!mp.count(get(i))) {
      mp[get(i)] = mp.size();
    }
  }
  for (int i = 0; i < N; ++i) {
    F[i] = mp[get(i)];
  }
  return F;
}

• 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