Submission #1252263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252263		jtnydv25	Migrations (IOI25_migrations)	C++20	97.45 / 100	31 ms	1004 KiB

migrations

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

#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif

const int N = 10000;
const int logN = 14;

int par[logN][N];
int depth[N];

int lca(int a, int b)
{
  if(depth[a]<depth[b])
  swap(a,b);
  int l = depth[a]-depth[b];
  for(int i = 0;i<logN;i++) if(l&(1<<i)) a = par[i][a];    
  if(a==b)
  return a;
  assert(depth[a] == depth[b]);
  for(int i = logN-1;i>=0;i--)
  if(par[i][a]!=par[i][b])
  {
    a = par[i][a],b = par[i][b];
  }
  return par[0][a];
}

int pathlen(int a, int b){
  return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}


vector<int> message, nodes;
vector<int> where;
int message_pos, a, b, where_a, where_b, id;
vector<pair<int, int>> pool, fin;
vector<vector<pair<int, int>>> parts;
vector<vector<int>> paths, nodes_groups;

void form_groups(int g){
  int L = nodes.size();
  nodes_groups.clear();
  nodes_groups.resize(g);
  int l = (L + g - 1) / g;
  for(int i = 0; i < L; i++){
    nodes_groups[i % g].push_back(nodes[i]);
    where[nodes[i]] = i % g;
  }
  for(int i = 0; i < g; i++) if(sz(nodes_groups[i]) < l){
    nodes_groups[i].push_back(nodes.back());
  }
}

void get(int ID, int l, int max_non_zero){
    vector<int> msg, pos, pos2, msg2;
    function<void(int)> recurse = [&](int i){
        ID--;
        if(ID == -1){
            msg2 = msg;
            pos2 = pos;
            return;
        }
        if(i == max_non_zero) return;
        // next non-zero
        int prv = i == 0 ? -1: pos[i - 1];
        for(int j = prv + 1; j < l; j++){
            for(int v = 1; v <= 4; v++){
                msg.push_back(v);
                pos.push_back(j);
                recurse(i + 1);
                msg.pop_back();
                pos.pop_back();
            }
        }
    };
    recurse(0);
    int j = 0;
    message.resize(l);
    fill(all(message), 0);
    for(int i = 0; i < sz(msg2); i++){
        message[pos2[i]] = msg2[i];
    }
    message_pos = 0;
}


int send_message(int n, int i, int Pi) {
  par[0][i] = Pi;
  depth[i] = depth[Pi] + 1;
  for(int j = 1; j < logN; j++) {
    par[j][i] = par[j - 1][par[j - 1][i]];
  }
  int d_ab = pathlen(a, b);
  int d_ia = pathlen(i, a);
  int d_ib = pathlen(i, b);
  if(d_ia >= max(d_ib, d_ab)){
    b = i;
  }
  else if(d_ib >= max(d_ia, d_ab)){
    a = i;
  }
  if(a < b) swap(a, b);
  
  vector<int> L = {215, 17, 4, 3, 2};
  vector<int> K = {1, 2, 2, 2};
  vector<int> G = {41, 64, 13, 10};
  vector<int> S = {215 + 17 + 4 + 3 + 2, 17 + 4 + 3 + 2, 4 + 3 + 2, 3 + 2, 2};
  vector<int> T = {n - S[0], n - S[1], n - S[2], n - S[3], n - S[4]};
  
  if(i < T[0]) return 0;
  for(int r = 0; r <= 3; r++){
    
    if(i == T[r]){
      if(r == 0){
        nodes.resize(n);
        iota(all(nodes), 0);
        where.resize(n);
      } else{
        nodes = nodes_groups[where_a];
        copy(all(nodes_groups[where_b]), back_inserter(nodes));
        for(int j = T[r - 1] + 1; j <= T[r]; j++) nodes.push_back(j);
      }
      form_groups(G[r]);
      where_a = where[a];
      where_b = where[b];
      int l = (nodes.size() + G[r] - 1) / G[r];
      if(where_a < where_b) swap(where_a, where_b);
      id = (where_a * (where_a + 1)) / 2 + where_b;
      get(id, L[r], K[r]);
    }
    if(i < T[r + 1]) return message[message_pos++];
  }
  
  if(i == T[4]){
      set<int> st;
      for(int j = T[3] + 1; j <= T[4]; j++) st.insert(j);
      for(int x: nodes_groups[where_a]) st.insert(x);
      for(int x: nodes_groups[where_b]) st.insert(x);
      assert(st.size() <= 5);
      nodes = vector<int>(all(st));
      while(nodes.size() < 5) nodes.push_back(nodes.back());
      paths = {
        {1, 0, 4},
        {1, 2, 3},
        {0, 2, 4},
        {3, 4, 1},
        {1, 3, 0}
      };
      id = -1;
      for(int ii = 0; ii < paths.size(); ii++){
        vector<int> path = paths[ii];
        vector<int> newpath = path;
        for(int j = 0; j < sz(path); j++){
          newpath[j] = nodes[path[j]];
        }
        vector<pair<int, int>> part;
        for(int j = 0; j + 1 < path.size(); j++){
          int u = nodes[path[j]];
          int v = nodes[path[j + 1]];
          if(u < v) swap(u, v);
          part.push_back({u, v});
          if(a == u && b == v) id = ii;
        }
        paths[ii] = newpath;
        parts.push_back(part);
      }
      assert(id != -1);
      return id;
  }

  if(i == T[4] + 1){
    vector<int> path = paths[id];
    fin = parts[id];
    fin.push_back({path[0], i});
    fin.push_back({path[1], i});
    fin.push_back({path[2], i});
    for(auto& it: fin){
      if(it.first < it.second) swap(it.first, it.second);
    }
    sort(all(fin));
    id = -1;
    for(int j = 0; j < fin.size(); j++){
      if(fin[j].first == a && fin[j].second == b){
        id = j;
        break;
      }
    }
    assert(id != -1);
    return id;
  }
  return 0;
}

int getID(int l, int max_non_zero) {
    vector<int> msg, pos, pos2, msg2;
    for(int i = 0; i < l; i++) if(message[i] != 0) {
        pos2.push_back(i);
        msg2.push_back(message[i]);
    }
    int ID = -1;
    int cur = -1;
    function<void(int)> recurse = [&](int i){
      cur++;
      if(msg == msg2 && pos == pos2) {
        ID = cur;
        return;
      }
      if(i == max_non_zero) return;
      // next non-zero
      int prv = i == 0 ? -1: pos[i - 1];
      for(int j = prv + 1; j < l; j++){
          for(int v = 1; v <= 4; v++){
              msg.push_back(v);
              pos.push_back(j);
              recurse(i + 1);
              msg.pop_back();
              pos.pop_back();
          }
      }
      
    };
    recurse(0);
    return ID;
}

std::pair<int, int> longest_path(std::vector<int> Q) {
  int n = 10000;
  vector<int> L = {215, 17, 4, 3, 2};
  vector<int> K = {1, 2, 2, 2};
  vector<int> G = {41, 64, 13, 10};
  vector<int> S = {215 + 17 + 4 + 3 + 2, 17 + 4 + 3 + 2, 4 + 3 + 2, 3 + 2, 2};
  vector<int> T = {n - S[0], n - S[1], n - S[2], n - S[3], n - S[4]};
  
  nodes.resize(n);
  iota(all(nodes), 0);
  where.resize(n);
  for(int r = 0; r <= 3; r++){
    if(r == 0){
      nodes.resize(n);
      iota(all(nodes), 0);
      where.resize(n);
    } else{
      nodes = nodes_groups[where_a];
      copy(all(nodes_groups[where_b]), back_inserter(nodes));
      for(int j = T[r - 1] + 1; j <= T[r]; j++) nodes.push_back(j);
    }
    form_groups(G[r]);
    message.clear();
    for(int j = T[r]; j < T[r + 1]; j++){
      message.push_back(Q[j]);
    }
    int ID = getID(L[r], K[r]);
    for(int u = 0; u < G[r]; u++){
      if(u * (u + 1) / 2 + u + 1 > ID){
        where_a = u;
        where_b = ID - u * (u + 1) / 2;
        break;
      }
    }
    form_groups(G[r]);
  }

  set<int> st;
  for(int j = T[3] + 1; j <= T[4]; j++) st.insert(j);
  for(int x: nodes_groups[where_a]) st.insert(x);
  for(int x: nodes_groups[where_b]) st.insert(x);
  assert(st.size() <= 5);
  nodes = vector<int>(all(st));
  while(nodes.size() < 5) nodes.push_back(nodes.back());

  paths = {
    {1, 0, 4},
    {1, 2, 3},
    {0, 2, 4},
    {3, 4, 1},
    {1, 3, 0}
  };

  for(int ii = 0; ii < paths.size(); ii++){
    vector<int> path = paths[ii];
    vector<int> newpath = path;
    for(int j = 0; j < sz(path); j++){
      newpath[j] = nodes[path[j]];
    }
    vector<pair<int, int>> part;
    for(int j = 0; j + 1 < path.size(); j++){
      int u = nodes[path[j]];
      int v = nodes[path[j + 1]];
      if(u < v) swap(u, v);
      part.push_back({u, v});
      if(a == u && b == v) id = ii;
    }
    paths[ii] = newpath;
    parts.push_back(part);
  }
  vector<int> path = paths[Q[T[4]]];
  vector<pair<int, int>> fin = parts[Q[T[4]]];
  fin.push_back({path[0], T[4] + 1});
  fin.push_back({path[1], T[4] + 1});
  fin.push_back({path[2], T[4] + 1});
  for(auto& it: fin){
    if(it.first < it.second) swap(it.first, it.second);
  }
  sort(all(fin));
  return fin[Q[N-1]];
}

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 67.4511 / 70