제출 #1289913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289913		avighna	스핑크스 (IOI24_sphinx)	C++20	100 / 100	526 ms	1600 KiB

sphinx

#include <bits/stdc++.h>

using namespace std;

int perform_experiment(vector<int> E);

int n;
vector<vector<int>> adj;

int query(const vector<int> &c) {
  if (find(c.begin(), c.end(), -1) != c.end()) {
    return perform_experiment(c);
  }
  int ans = 0;
  queue<int> q;
  vector<bool> vis(n);
  for (int i = 0; i < n; ++i) {
    if (vis[i]) {
      continue;
    }
    vis[i] = true;
    ans++;
    q.push(i);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int &i : adj[u]) {
        if (!vis[i] and c[u] == c[i]) {
          vis[i] = true;
          q.push(i);
        }
      }
    }
  }
  return ans;
}

class dsu {
private:
  int n;
  vector<int> par, size;
  vector<vector<int>> comp_m;

public:
  dsu(int n) : n(n), par(n), size(n, 1), comp_m(n) {
    iota(par.begin(), par.end(), 0);
    for (int i = 0; i < n; ++i) {
      comp_m[i].push_back(i);
    }
  }

  int root(int u) { return u == par[u] ? u : par[u] = root(par[u]); }

  void merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) {
      return;
    }
    if (size[u] < size[v]) {
      swap(u, v);
    }
    for (int &i : comp_m[v]) {
      comp_m[u].push_back(i);
    }
    par[v] = u;
    size[u] += size[v];
  }

  const vector<int> &comp(int u) { return comp_m[root(u)]; }
};

vector<int> find_colours(int N, vector<int> x, vector<int> y) {
  n = N;
  adj.resize(n);
  for (int i = 0; i < x.size(); ++i) {
    adj[x[i]].push_back(y[i]), adj[y[i]].push_back(x[i]);
  }

  dsu dsu(n);
  for (int u = 1; u < n; ++u) {
    vector<char> seen(n);
    vector<int> nodes;
    for (int &i : adj[u]) {
      if (int r = dsu.root(i); r <= u && !exchange(seen[r], true)) {
        nodes.push_back(r);
      }
    }
    auto has = [&](int from, int till) {
      vector<int> q(n, n);
      for (int i = from; i <= till; ++i) {
        for (int u : dsu.comp(nodes[i])) {
          q[u] = dsu.root(nodes[i]);
        }
      }
      q[u] = n + 1;
      int bef = query(q);
      for (int i = from; i <= till; ++i) {
        for (int u : dsu.comp(nodes[i])) {
          q[u] = -1;
        }
      }
      q[u] = -1;
      return bef - query(q);
    };
    for (int _ = 0, times = has(0, nodes.size() - 1), fr = -1; _ < times; ++_) {
      dsu.merge(u, nodes[fr = *ranges::partition_point(views::iota(fr + 1, int(nodes.size()) - 1), [&](int i) { return !has(fr + 1, i); })]);
    }
  }

  vector<vector<int>> nadj(n);
  for (int u = 0; u < n; ++u) {
    for (int &i : adj[u]) {
      if (dsu.root(u) != dsu.root(i)) {
        nadj[dsu.root(u)].push_back(dsu.root(i));
      }
    }
  }
  for (int u = 0; u < n; ++u) {
    sort(nadj[u].begin(), nadj[u].end());
    nadj[u].erase(unique(nadj[u].begin(), nadj[u].end()), nadj[u].end());
  }

  vector<int> dist(n);
  queue<int> q;
  vector<bool> vis(n);
  for (int i = 0; i < n; ++i) {
    if (vis[i] or dsu.root(i) != i) {
      continue;
    }
    vis[i] = true;
    q.push(i);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int &i : nadj[u]) {
        if (!vis[i]) {
          vis[i] = true;
          dist[i] = dist[u] + 1;
          q.push(i);
        }
      }
    }
  }

  vector<int> a, b;
  for (int u = 0; u < n; ++u) {
    if (dsu.root(u) != u) {
      continue;
    }
    (dist[u] & 1 ? a : b).push_back(u);
  }

  vector<int> ans(n);
  if (a.empty()) {
    for (int c = 0; c < n; ++c) {
      vector<int> q(n, -1);
      q[0] = c;
      if (query(q) == 1) {
        ans[b[0]] = c;
        break;
      }
    }
  } else {
    for (auto &[a, b] : array<pair<vector<int>, vector<int>>, 2>({{a, b}, {b, a}})) {
      for (int c = 0; c < n; c++) {
        int qq = -1;
        auto has = [&](int from, int till, bool setqq = false) {
          vector<int> q(n, n);
          for (int &i : b) {
            for (auto &u : dsu.comp(i)) {
              q[u] = n + 1;
            }
          }
          for (int i = from; i <= till; ++i) {
            for (auto &u : dsu.comp(a[i])) {
              q[u] = a[i];
            }
          }
          int bef = query(q);
          for (int &i : b) {
            for (auto &u : dsu.comp(i)) {
              q[u] = c;
            }
          }
          for (int i = from; i <= till; ++i) {
            for (auto &u : dsu.comp(a[i])) {
              q[u] = -1;
            }
          }
          int aft = query(q);
          if (setqq) {
            qq = bef - aft;
          }
          return bef - aft;
        };
        int fr = -1;
        while (true) {
          if (qq == 0) {
            break;
          }
          if (has(fr + 1, a.size() - 1, true) == 0) {
            break;
          }
          int rr = 0;
          fr = *ranges::partition_point(views::iota(fr + 1, int(a.size()) - 1), [&](int i) {
            int v = has(fr + 1, i);
            if (v != 0) {
              rr = v;
            }
            return v == 0;
          });
          qq -= rr;
          ans[a[fr]] = c;
        }
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    ans[i] = ans[dsu.root(i)];
  }
  return ans;
}

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