Submission #1279291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279291		avighna	Sphinx's Riddle (IOI24_sphinx)	C++20	1.50 / 100	20 ms	400 KiB

sphinx

#include <bits/stdc++.h>

int perform_experiment(std::vector<int> E);

int n;
std::vector<std::vector<int>> adj;

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

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

public:
  dsu(int n) : n(n), par(n), size(n, 1), comp_m(n) {
    std::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]){std::swap(u,v);}
    for (int &i:comp_m[v]){
      comp_m[u].push_back(i);
    }
    par[v]=u;
    size[u]+=size[v];
  }

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

std::vector<int> find_colours(int N, std::vector<int> x, std::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]);
  }

  std::queue<int> q;
  q.push(0);std::vector<bool> vis(n);
  std::vector<int> ord;
  while (!q.empty()){
    int u=q.front();
    q.pop();if (vis[u]){continue;}
    ord.push_back(u);
    vis[u]=true;
    for (int &i:adj[u]){
      q.push(i);
    }
  }

  dsu dsu(n);
  vis.assign(n,false);
  for (int i=1;i<n;++i){
    int u=ord[i];
    vis[u]=true;
    std::vector<bool> seen(n);
    std::vector<int> nodes;
    for (int i :adj[u]) {
      i=dsu.root(i);
      if (vis[i] or seen[i]){continue;}
      seen[i]=true;nodes.push_back(i);
    }
    auto has=[&](int till){
      std::vector<int> q(n,n);
      for (int i=0;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=0;i<=till;++i){
        for (int u:dsu.comp(nodes[i])){
          q[u]=-1;
        }
      }
      q[u]=-1;
      int aft=query(q);
      return bef!=aft;
    };
    int fr;
    if (!has(nodes.size()-1)) {
      fr=nodes.size();
    } else {
      fr=*std::ranges::partition_point(std::views::iota(0,int(nodes.size())),[&](int i) {
      return !has(i);
    });}
    if (fr!=nodes.size()){dsu.merge(u,nodes[fr]);}
  }

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

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