Submission #1251272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251272		jtnydv25	Migrations (IOI25_migrations)	C++20	0 / 100	857 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<pair<int, int>> pool;
vector<int> L = {221, 13};
const int T1 = N - (4 + 13 + 221);
const int T2 = N - (4 + 13);
const int T3 = N - 4;
int a, b, P, Q, R;
int A, B;

vector<int> message;
int message_pos;
int pos_4;
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 <= 3; 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);
    for(int i = 0; i < sz(msg2); i++){
        message[pos2[i]] = msg2[i];
    }
    message_pos = 0;
    pos_4 = -1;
}
vector<vector<int>> cliques_6, cliques_4, paths;
vector<vector<pair<int, int>>> parts;
int id = -1;
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);
  // trace(i, a, b);
  if(i < T1) return 0;
  if(i == T1){
    A = a; B = b;
    int ID = (a * (a - 1)) / 2 + b;
    get(ID, L[0], 3); // cost = 3
  }

  if(i < T2){
    if(i != T1){
      if(a == i || b == i){
        if(a != A && a != B && b != A && b != B){
          pos_4 = i;
          return 4;
        }
      }
    }
    return message[message_pos++];
  }

  if(i == T2){
    // trace(pos_4);
    // compute the pool
    P = A, Q = B, R = i;
    pool.clear();
    if(pos_4 != -1){
      P = pos_4; Q = pos_4;
    }
    pool.push_back({P, Q});
    pool.push_back({P, R});
    pool.push_back({Q, R});
    for(int j = T1; j < T2; j++){
      pool.push_back({P, j});
      pool.push_back({Q, j});
      pool.push_back({R, j});
    }
    for(auto& it: pool){
      if(it.first < it.second) swap(it.first, it.second);
    }
    sort(all(pool));

    if(a < b) swap(a, b);
    A = a; B = b;
    int ID = -1;
    for(int i = 0; i < pool.size(); i++){
      if(pool[i].first == a && pool[i].second == b){
        ID = i;
        break;
      }
    }
    // trace(A, B);
    assert(ID != -1);
    get(ID, L[1], 2); // cost = 2
  }

  if(i < T3){
    if(i != T2){
      if(a == i || b == i){
        if(a != A && a != B && b != A && b != B){
          pos_4 = i;
          return 4;
        }
      }
    }
    return message[message_pos++];
  }

  
  if(i == T3){
    P = A, Q = B, R = i;
    if(pos_4 != -1){
      P = pos_4; Q = pos_4;
    }
    // cover using K6 graphs
    // T2 + 1, ... i - 1 -- 12 nodes
    // P Q R
    
    cliques_6 = {
      {P, Q, R, T2 + 1, T2 + 2, T2 + 3},
      {P, Q, R, T2 + 4, T2 + 5, T2 + 6},
      {P, Q, R, T2 + 7, T2 + 8, T2 + 9},
      {P, Q, R, T2 + 10, T2 + 11, T2 + 12},
      {P, Q, R, T2 + 1, T2 + 2, T2 + 3}
    };
    // trace(cliques_6);
    // trace(cliques_6, pos_4);
    for(int i = 0; i < 5; i++){
      if(find(all(cliques_6[i]), a) != cliques_6[i].end() &&
          find(all(cliques_6[i]), b) != cliques_6[i].end()){
          id = i;
          break;
        }
    }
    assert(id != -1);
    return id;
  }
  if(i == T3 + 1){
    vector<int> nodes = cliques_6[id];
    nodes.push_back(i);
    cliques_4 = {
      {nodes[0], nodes[1], nodes[2], nodes[3]},
      {nodes[0], nodes[1], nodes[2], nodes[4]},
      {nodes[0], nodes[1], nodes[2], nodes[5]},
      {nodes[0], nodes[1], nodes[2], nodes[6]},
      {nodes[3], nodes[4], nodes[5], nodes[6]}
    };
    // trace(cliques_4);
    id = -1;
    for(int i = 0; i < 5; i++){
      if(find(all(cliques_4[i]), a) != cliques_4[i].end() &&
          find(all(cliques_4[i]), b) != cliques_4[i].end()){
          id = i;
          break;
        }
    }
    assert(id != -1);
    return id;
  }
  if(i == T3 + 2){
    vector<int> nodes = cliques_4[id];
    nodes.push_back(i);
    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, parts);
    assert(id != -1);
    return id;
  }
  vector<pair<int, int>> fin;
  if(i == T3 + 3){
    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));
    // trace(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);
    // 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 <= 3; 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> S) {
  // return {0, 3};
  a, b = 0, 0;
  message.clear();
  pos_4 = -1;
  for(int i = T1; i < T2; i++){
    message.push_back(S[i]);
    if(S[i] == 4) pos_4 = i;
  }
  if(pos_4 != -1){
    P = pos_4; Q = pos_4; R = T2;
  } else{
    int ID = getID(L[0], 3);
    
    for(int _a = 1; _a < N; _a++){
      for(int _b = 0; _b < _a; _b++){
        ID--;
        if(ID == -1){
          a = _a;
          b = _b;
          break;
        }
      }
    }
    P = a; Q = b; R = T2;
  }

  pool.clear();
  pool.push_back({P, Q});
    pool.push_back({P, R});
    pool.push_back({Q, R});
    for(int j = T1; j < T2; j++){
      pool.push_back({P, j});
      pool.push_back({Q, j});
      pool.push_back({R, j});
    }
    for(auto& it: pool){
      if(it.first < it.second) swap(it.first, it.second);
    }
    sort(all(pool));

    message.clear();
    pos_4 = -1;
    for(int i = T2; i < T3; i++){
        message.push_back(S[i]);
        if(S[i] == 4) pos_4 = i;
    }

    if(pos_4 != -1){
      P = pos_4; Q = pos_4; R = T3;
    } else{
      int ID = getID(L[1], 2);
      a = pool[ID].first;
      b = pool[ID].second;
      P = a; Q = b; R = T3;
    }
    cliques_6 = {
      {P, Q, R, T2 + 1, T2 + 2, T2 + 3},
      {P, Q, R, T2 + 4, T2 + 5, T2 + 6},
      {P, Q, R, T2 + 7, T2 + 8, T2 + 9},
      {P, Q, R, T2 + 10, T2 + 11, T2 + 12},
      {P, Q, R, T2 + 1, T2 + 2, T2 + 3}
    };
    // trace(cliques_6, pos_4);
    id = S[T3];
    vector<int> nodes = cliques_6[id];
    nodes.push_back(T3 + 1);
    cliques_4 = {
      {nodes[0], nodes[1], nodes[2], nodes[3]},
      {nodes[0], nodes[1], nodes[2], nodes[4]},
      {nodes[0], nodes[1], nodes[2], nodes[5]},
      {nodes[0], nodes[1], nodes[2], nodes[6]},
      {nodes[3], nodes[4], nodes[5], nodes[6]}
    };
    id = S[T3 + 1];
    nodes = cliques_4[id];
    nodes.push_back(T3 + 2);
    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});
      }
      paths[ii] = newpath;
      parts.push_back(part);
    }
    id = S[T3 + 2];
    vector<int> path = paths[id];
    vector<pair<int, int>> fin = parts[id];
    fin.push_back({path[0], T3 + 3});
    fin.push_back({path[1], T3 + 3});
    fin.push_back({path[2], T3 + 3});
    for(auto& it: fin){
      if(it.first < it.second) swap(it.first, it.second);
    }
    sort(all(fin));
    id = S[T3 + 3];
    // trace(cliques_6, cliques_4, paths, parts, fin);
    return {fin[id].first, fin[id].second};
}

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