제출 #1204277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204277		abczz	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	269 ms	1528 KiB

sphinx

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

using namespace std;

vector <int> E;
map <ll, ll> mp;
vector <ll> adj[250];
bool visited[250], C[250][250];
ll n, P[250], X[250], ty[250];

ll dsu(ll u) {
  if (P[u] == u) return u;
  else return P[u] = dsu(P[u]);
}
void color(ll u) {
  for (int i=0; i<n; ++i) E[i] = u;
}
void dfs(ll u, ll w) {
  ty[u] = w;
  for (auto v : adj[u]) {
    if (X[v] == -1) {
      if (!w) X[u] = v, X[v] = u;
      else X[v] = u;
      dfs(v, w^1);
    }
  }
}
void dfs2(ll u) {
  visited[u] = 1;
  for (auto v : adj[u]) {
    if (!visited[v] && E[u] == E[v] && (E[u] != -1 || dsu(u) == dsu(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]) {
      ++tot;
      visited[i] = 1;
      if (E[i] != -1) dfs2(i);
    }
  }
  return tot;
}
std::vector<int> find_colours(int N, std::vector<int> ex, std::vector<int> ey) {
  n = N;
  vector <int> F;
  F.resize(n);
  E.resize(n);
  for (int i=0; i<n; ++i) P[i] = i, ty[i] = X[i] = F[i] = -1;
  for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) C[i][j] = 0;
  for (int i=0; i<ex.size(); ++i) {
    adj[ex[i]].push_back(ey[i]);
    adj[ey[i]].push_back(ex[i]);
    C[ex[i]][ey[i]] = C[ey[i]][ex[i]] = 1;
  }
  for (int i=1; i<n; ++i) {
    mp.clear();
    for (int j=0; j<i; ++j) {
      if (C[j][i]) mp[dsu(j)] = j;
    }
    if (mp.empty()) continue;
    vector <ll> V;
    for (auto [x, y] : mp) V.push_back(y);
    while (!V.empty()) {
      color(n);
      E[i] = -1;
      for (auto u : V) E[u] = -1;
      if (perform_experiment(E) == count()) break;
      ll l = 0, r = (ll)V.size()-1, mid;
      while (l < r) {
        mid = (l+r)/2;
        color(n);
        E[i] = -1;
        for (int x=l; x<=mid; ++x) E[V[x]] = -1;
        if (perform_experiment(E) == count()) l = mid+1;
        else r = mid;
      }
      P[dsu(V[l])] = dsu(i);
      swap(V[l], V[(ll)V.size()-1]);
      V.pop_back();
    }
  }
  dfs(0, 0);
  vector <ll> V[2];
  for (int i=0; i<n; ++i) {
    if (dsu(i) == i) {
      V[ty[i]].push_back(i);
    }
  }
  for (int x=0; x<2; ++x) {
    for (int c=0; c<n; ++c) {
      while (!V[x].empty()) {
        color(n);
        for (auto u : V[x]) E[u] = -1, E[X[u]] = c;
        if (perform_experiment(E) == count()) break;
        ll l = 0, r = (ll)V[x].size()-1, mid;
        while (l < r) {
          mid = (l+r)/2;
          color(n);
          for (int i=l; i<=mid; ++i) E[V[x][i]] = -1, E[X[V[x][i]]] = c;
          if (perform_experiment(E) == count()) l = mid+1;
          else r = mid;
        }
        F[V[x][l]] = c;
        swap(V[x][l], V[x][(ll)V[x].size()-1]);
        V[x].pop_back();
      }
    }
  }
  for (int i=0; i<n; ++i) {
    if (F[i] == -1) F[i] = F[dsu(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