Submission #1210089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210089		trimkus	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	513 ms	1984 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];
vector<int> adj1[MAXN];
int parity[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;
  stack<int> st;
  for (int i = 0; i < N; ++i) vis[i] = false;
  for (int i = 0; i < N; ++i) {
    if (!vis[i]) {
      cnt++;
      st.push(i);
      while (st.size()) {
        int v = st.top();
        vis[v] = true;
        bool added = false;
        for (auto& u : adj[v]) {
          if (vis[u]) continue;
          if (color(u) != color(v)) continue;
          added = true;
          st.push(u);
          break;
        }
        if (!added) {
          st.pop();
        }
      }
    }
  }
  return cnt;
}

void get_parity() {
  stack<int> st;
  for (int i = 0; i < N; ++i) vis[i] = false;
  for (int i = 0; i < N; ++i) {
    if (!vis[i]) {
      st.push(i);
      while (st.size()) {
        int v = st.top();
        vis[v] = true;
        bool added = false;
        for (auto& u : adj1[v]) {
          if (vis[u]) continue;
          added = true;
          st.push(u);
          parity[u] = parity[v] ^ 1;
          break;
        }
        if (!added) {
          st.pop();
        }
      }
    }
  }
}

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;
      // cerr << "Checking if there are no vertices with the same color as " << i << "\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;
      st.clear();
      for (int j = 0; j < i; ++j) {
        if (get(j) != i) {
          st.insert(get(j));
        }
      }
      pool.clear();
      while (st.size()) {
        pool.push_back(*begin(st));
        st.erase(begin(st));
      }
      assert((int)pool.size() > 0);
      for (auto& u : pool) {
        assert(get(u) == u);
      }
      // 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;
        }
        assert(mid >= 0);
        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;
        }
        // cerr << "Starting experiment... -> ";
        if (expected() == perform_experiment(E)) {
          left = mid + 1;
        } else {
          right = mid;
        }
        // cerr << "Finished, with = [" << left << ", " << right << "]\n";
      }
      // cerr << "Found parent for = " << get(pool[right]) << ", the parent is = " << i << "\n";
      assert(get(pool[right]) != i);
      p[get(pool[right])] = i;
    }
  }
  set<int> supernodes;
  for (int i = 0; i < N; ++i) {
    supernodes.insert(get(i));
  }
  if (supernodes.size() == 1) {
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        E[j] = i;
      }
      E[0] = -1;
      if (perform_experiment(E) == 1) {
        for (int j = 0; j < N; ++j) {
          F[j] = i;
        }
        break;
      }
    }
  } else {
    for (int i = 0; i < N; ++i) {
      for (auto& u : adj[i]) {
        if (get(u) == get(i)) continue;
        adj1[get(u)].push_back(get(i));
        adj1[get(i)].push_back(get(u));
      }
    }
    get_parity();
    for (int i = 0; i < N; ++i) {
      cerr << parity[get(i)] << " ";
    }
    cerr << "\n";
    // subtask 3 but on a tree
    for (int par = 0; par < 2; ++par) {
      for (int i = 0; i < N; ++i) {
        while (true) {
          for (int j = 0; j < N; ++j) {
            if (F[get(j)] != -1 || parity[get(j)] == par) {
              E[j] = i;
            } else {
              E[j] = -1;
            }
          }
          cerr << "Checking color " << i << " for parity " << par << ": ";
          for (auto u : E) {
            cerr << u << " ";
          }
          cerr << "\n";
          if (expected() == perform_experiment(E)) {
            break;
          }
          set<int> st;
          vector<int> pool;
          for (int j = 0; j < N; ++j) {
            if (parity[get(j)] == par ^ 1 && F[get(j)] == -1) {
              st.insert(get(j));
            }
          }
          while (st.size()) {
            pool.push_back(*begin(st));
            st.erase(begin(st));
          }
          int left = 0, right = (int)pool.size() - 1;
          cerr << "Pool: ";
          for (auto& u : pool) {
            cerr << u << " ";
          }
          cerr << "\n";
          while (left < right) {
            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]] = true;
            }
            for (int j = 0; j < N; ++j) {
              if (online[get(j)]) {
                E[j] = -1;
              } else {
                E[j] = i;
              }
            }
            if (expected() == perform_experiment(E)) {
              left = mid + 1;
            } else {
              right = mid;
            }
          }
          F[pool[right]] = i;
        }
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    F[i] = F[get(i)];
  }
  return F;
}

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