Submission #1265206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265206		madamadam3	Migrations (IOI25_migrations)	C++20	86.40 / 100	60 ms	3476 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

void dfs(int u, int p, vi &dist, vvi &adj) {
  for (auto &v : adj[u]) {
    if (v == p) continue;
    dist[v] = dist[u] + 1;
    dfs(v, u, dist, adj);
  }
}

int furthest_from(int u, int n, vvi &adj) {
  vector<int> dist(n);
  dfs(u, u, dist, adj);

  int f = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f]) f = i;
  return f;
}

int dist_between(int n, int u, int v, vvi &adj) {
  vector<int> dist(n);
  dfs(u, u, dist, adj);

  return dist[v];
}

pi furthest_pair(int n, vvi &adj) {
  vector<int> dist(n);
  dfs(0, 0, dist, adj);
  int f1 = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f1]) f1 = i;
  dist = vi(n, 0);
  dfs(f1, f1, dist, adj);
  int f2 = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f2]) f2 = i;

  return {min(f1, f2), max(f1, f2)};
}

vi to_base(ll A, ll b, int pad = 0) {
  vi ans;
  while (A > 0LL) {
    ans.push_back(A % b);
    A /= b;
  }
  
  while (ans.size() < pad) ans.push_back(0);
  return ans;
}

ll from_base(vi bx, ll b) {
  ll po = 1;
  ll ans = 0;

  for (auto &el : bx) {
    ans += ll(el) * po;
    po *= b;
  }

  return ans;
}

const int CN = 12, CK = 3;
map<int, pair<int, uint64_t>> rank_to_mask;
map<pair<int, uint64_t>, int> mask_to_rank;

void initialise_ranks(int N, int K) {
  rank_to_mask.clear(); mask_to_rank.clear();
  uint64_t initial = 0;

  int counter = 0;
  auto dfs = [&](const auto &self, int type, uint64_t cur, int idx, int rem) {
  if (rem == 0) {
      rank_to_mask[counter] = {type, cur};
      mask_to_rank[{type, cur}] = counter++;
      return;
    }

    for (int i = idx; i < N; i++) {
      uint64_t nxt = cur | (1LL << i);
      self(self, type, nxt, i+1, rem-1);
    }
  };

  for (int i = 0; i < 64; i++) {
    dfs(dfs, i, initial, 0, K);
  }
}

vvi adj;
pi fr;
int diam = 0, cpos = 0;
int U = 0, V = 0, rU = 0, rV = 0;
vector<int> change_types;

int x = 0, actual_step = 0;
bool changed = false;
int send_message(int n, int i, int Pi) {
  if (i <= 1) {
    adj.assign(n+1, vi());
    initialise_ranks(CN, CK);
  }
  x = n - 33;

  adj[Pi].push_back(i);
  adj[i].push_back(Pi);

  if (i < x) return 0;
  int step = actual_step++;

  if (step == 0) {
    fr = furthest_pair(n, adj); diam = dist_between(n, fr.first, fr.second, adj); 
    U = fr.first; V = fr.second;
    rU = U, rV = V;
  } else if (step == 14) {
    rV = V = furthest_from(U, n, adj);
  }

  pi cfr = furthest_pair(n, adj);
  int u = cfr.first, v = cfr.second;
  int cdiam = dist_between(n, u, v, adj);

  int type = cdiam == diam ? 0 : (dist_between(n, i, V, adj) == cdiam ? 1 : 2); // if the diameter changed, did we switch u or v
  change_types.push_back(type);
  diam = cdiam;

  if (type == 1) {
    U = i;
  } else if (type == 2) {
    V = i;
    if (step < 14) U = V;
  }

  // cout << "Step: " << step << " U: " << U << " V: " << V << "\n";

  vi u12 = to_base(rU, 12, 4), v2 = to_base(rV, 2, 14);

  auto mask1 = rank_to_mask[rU];
  vector<int> umask(12, 0); 
  int ones_seen = 0; for (int i = 0; i < 12; i++) {
    if (!(mask1.second & (1LL << i))) continue;
    vi l4 = to_base(mask1.first, 4, 3);

    umask[i] = l4[ones_seen]+1;
    ones_seen++;
  }

  auto mask2 = rank_to_mask[rV];
  vector<int> vmask(12, 0); 
  ones_seen = 0; for (int i = 0; i < 12; i++) {
    if (!(mask2.second & (1LL << i))) continue;
    vi l4 = to_base(mask2.first, 4, 3);

    vmask[i] = l4[ones_seen]+1;
    ones_seen++;
  }

  // cout << "mask1 - f: " << mask1.first << " s: "; for (int idx = 0; idx < 12; idx++) cout << min(1UL, mask1.second & (1 << idx)) << " "; cout << "\n";
  // cout << "mask2 - f: " << mask2.first << " s: "; for (int idx = 0; idx < 12; idx++) cout << min(1UL, mask2.second & (1 << idx)) << " "; cout << "\n"; 

  if (step < 12) {
    return umask[step];
  } else if (step < 14) {
    int px = 14; for (int k = 0; k < 12; k++) if (change_types[k] != 0) px = k;
    int a = px / 3, b = px % 3;

    if (step == 12) return a;
    else if (change_types[13] != 0) return 4;
    else if (change_types[12] != 0) return 3;
    else return b;  
  } else if (step < 26) {
    return vmask[step - 14];
  } else if (step < 28) {
    int px = 14; for (int k = 0; k < 12; k++) if (change_types[14+k] == 1) px = k;
    int a = px / 3, b = px % 3;

    if (step == 26) return a;
    else if (change_types[27] == 1) return 4;
    else if (change_types[26] == 1) return 3;
    else return b;  
  } else if (step < 30) {
    int px = 14; for (int k = 0; k < 14; k++) if (change_types[14+k] == 2) px = k;
    int a = px / 3, b = px % 3;

    if (step == 28) return a;
    else if (change_types[29] == 2) return 4;
    else if (change_types[28] == 2) return 3;
    else return b;  
  } else if (step == 30) {
    if (type == 0) {
      if (change_types[29] == 1) return 1;
      else if (change_types[28] == 1) return 2;
      else return 0;
    } else if (type == 1) {
      return 0;
    } else {
      if (change_types[29] == 1) return 3;
      else if (change_types[28] == 1) return 4;
      else return 0;
    }
  } else if (step == 31) {
    if (type == 0) {
      if (change_types[30] == 1) return 0;
      else return 1;
    } else if (type == 1) {
      return 2;
    } else {
      if (change_types[30] == 1) return 3;
      else return 4;
    }
  } else if (step == 32) {
    if (type == 0) {
      if (change_types[30] == 2 && change_types[31] != 2) return 0;
      else return 1;
    } else if (type == 1) {
      if (change_types[30] == 2 && change_types[31] != 2) return 2;
      else return 3;
    } else {
      return 4;
    }
  }
}

// 0 - no change, 1 - change u, 2 - change v
pi longest_path(vi S) {
  initialise_ranks(CN, CK);

  int n = S.size();
  int x = n - 33;

  pair<int, uint64_t> mask1 = {0, 0}, mask2 = {0, 0};
  vector<int> l4, c4; 

  for (int i = 0; i < 12; i++) {
    if (S[x+i] == 0) continue;
    mask1.second |= (1LL << i);
    l4.push_back(S[x+i]-1);
  }

  for (int i = 14; i < 26; i++) {
    if (S[x+i] == 0) continue;
    mask2.second |= (1LL << (i - 14));
    c4.push_back(S[x+i]-1);
  }

  mask1.first = from_base(l4, 4);
  mask2.first = from_base(c4, 4);

  // cout << "mask1 - f: " << mask1.first << " s: "; for (int idx = 0; idx < 12; idx++) cout << min(1UL, mask1.second & (1 << idx)) << " "; cout << "\n";
  // cout << "mask2 - f: " << mask2.first << " s: "; for (int idx = 0; idx < 12; idx++) cout << min(1UL, mask2.second & (1 << idx)) << " "; cout << "\n"; 

  int u = mask_to_rank[mask1], v = mask_to_rank[mask2];

  if (S[x+13] == 3) u = x+12;
  else if (S[x+13] == 4) u = x+13;
  else if (!(S[x+12] == 4 && S[x+13] == 2)) u = x + (S[x+12] * 3 + S[x+13]); 

  if (S[x+27] == 3) u = x+26;
  else if (S[x+27] == 4) u = x+27;
  else if (!(S[x+26] == 4 && S[x+27] == 2)) u = x + 14 + (S[x+26] * 3 + S[x+27]); 

  if (S[x+29] == 3) v = x+28;
  else if (S[x+29] == 4) v = x+29;
  else if (!(S[x+28] == 4 && S[x+29] == 2)) v = x + 14 + (S[x+28] * 3 + S[x+29]); 

  if (S[x+30] == 1) u = x + 29;
  else if (S[x+30] == 2) u = x + 28;
  else if (S[x+30] == 3) {v = x+30; u = x+29;}
  else if (S[x+30] == 4) {v = x+30; u = x+28;}

  if (S[x+31] == 0) u = x+30;
  else if (S[x+31] == 2) u = x+31;
  else if (S[x+31] == 3) {v = x+31; u = x+30;}
  else if (S[x+31] == 4) v = x+31;

  if (S[x+32] == 0) v = x+30;
  else if (S[x+32] == 2 && v != x + 31) {u = x+32; v = x+30;}
  else if (S[x+32] == 3) u = x+32;
  else if (S[x+32] == 4) v = x+32;

  // auto bp = furthest_pair(n, adj);
  // if (!(dist_between(n, u, v, adj) == dist_between(n, bp.first, bp.second, adj))) {
  //   cout << "failure!\n";
  // }
  int A = u, B = v;
  return {A, B}; 
}

Compilation message (stderr)

migrations.cpp: In function 'int send_message(int, int, int)':
migrations.cpp:227:1: warning: control reaches end of non-void function [-Wreturn-type]
  227 | }
      | ^

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