Submission #1251556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251556		jtnydv25	Migrations (IOI25_migrations)	C++20	93.11 / 100	895 ms	1220 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;
int message_pos, a, b, A, B, id;
vector<pair<int, int>> pool, fin;
vector<vector<pair<int, int>>> parts;
vector<vector<int>> paths;

void get(int ID, int l, int max_non_zero){
  trace(ID, l, 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);
    // trace(pos2, msg2, ID);
    int j = 0;
    // message.resize(l, 0);
    message.resize(l);
    fill(all(message), 0);
    // trace(sz(msg2));
    trace(msg2.size(), ID);
    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) {
  // trace(n, i, 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 = {167, 12, 3, 2};
  vector<int> S = {167+12 + 3 + 2, 12 + 3 + 2, 3 + 2, 2};
  vector<int> T = {N - S[0], N - S[1], N - S[2], N - S[3]};
  if(i < T[0]) return 0;
  if(i == T[0]){
    A = a; B = b;
    trace(A, B);
    int ID = (A * (A - 1)) / 2 + B;
    get(ID, L[0], 3);
  }
  if(i < T[1])
    return message[message_pos++];
  for(int r = 1; r < 4; r++){
    if(i == T[r]){
      pool.clear();
      trace(r);
      nodes = {A, B};
      id = -1;
      for(int j = T[r - 1] + 1; j <= T[r]; j++) nodes.push_back(j);
      for(int j = 0; j <nodes.size(); j++) {
        for(int k = j + 1; k < nodes.size(); k++) {
          int u = nodes[j], v = nodes[k];
          if(u < v) swap(u, v);
          if(u == a && v == b) id = pool.size();
          pool.push_back({u, v});
        }
      }
      A =a; B = b;
      trace(A, B, nodes.size(), id);
      get(id, L[r], 3);
    }
  }
  if(i < T[3]) return message[message_pos++];

  if(i == T[3]){
      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);
      }
      trace(paths, id);
      assert(id != -1);
      return id;
  }

  if(i == T[3] + 1){
    vector<int> path = paths[id];
    trace(path);
    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;
      }
    }
    trace(fin, id);
    assert(id != -1);
    trace(a, b);
    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) {
  vector<int> L = {167, 12, 3, 2};
  vector<int> S = {167+12 + 3 + 2, 12 + 3 + 2, 3 + 2, 2};
  vector<int> T = {N - S[0], N - S[1], N - S[2], N - S[3]};
  int non_zero_count = 0;
  for(int i = 1; i < S.size(); i++) {
    if(S[i] != 0) non_zero_count++;
  }
  // return {0, 3};
  a, b = 0, 0;
  message.clear();
  for(int i = 0; i < 3; i++){
    message.clear();
    for(int j = T[i]; j < T[i + 1]; j++){
      message.push_back(Q[j]);
    }
    int ID = getID(L[i], 3);
    if(i > 0){
      a = pool[ID].first;
      b = pool[ID].second;
    } else{
      for(int _a = 1; _a < N && ID >= 0; _a++){
        for(int _b = 0; _b < _a; _b++){
          ID--;
          if(ID == -1){
            a = _a;
            b = _b;
            break;
          }
        }
      }
    }
    trace(a, b);
    pool.clear();
    nodes = {a, b};
    for(int j = T[i] + 1; j <= T[i + 1]; j++) {
      nodes.push_back(j);
    }

    for(int j = 0; j < nodes.size(); j++) {
      for(int k = j + 1; k < nodes.size(); k++) {
        int u = nodes[j], v = nodes[k];
        if(u < v) swap(u, v);
        pool.push_back({u, v});
      }
    }
  }
  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);
  }
  trace(paths);
  vector<int> path = paths[Q[T[3]]];
  trace(path);
  vector<pair<int, int>> fin = parts[Q[T[3]]];
  fin.push_back({path[0], T[3] + 1});
  fin.push_back({path[1], T[3] + 1});
  fin.push_back({path[2], T[3] + 1});
  for(auto& it: fin){
    if(it.first < it.second) swap(it.first, it.second);
  }
  sort(all(fin));
  trace(fin, Q[N-1]);
  return fin[Q[N-1]];
}

// }

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