Submission #1252600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252600		bynix	Migrations (IOI25_migrations)	C++20	30 / 100	31 ms	1716 KiB

migrations

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

vector<pair<int, int>> map66;
vector<vector<int>> adj;
vector<int> pow5;

int c1, c2;
int d1, d2;

#define upd {adj[i].push_back(Pi); adj[Pi].push_back(i);}

#define Q(k, l) ((d1 == k && d2 == l) || (d1 == l && d2 == k))
#define R(k, l) (u == k && v == l)

const int p = 9994, q = 9995, r = 9996;;
const int a = 9997, b = 9998, c = 9999;

int A, B, C;

void dfs(int cur, int par, vector<vector<int>>& adj, vector<int>& depth, int dep){
  depth[cur] = dep;
  for (auto &e: adj[cur]) if (e != par) dfs(e, cur, adj, depth, dep + 1);
}

pair<int, int> diameter(){
  vector<int> depth(10000, 0), depth2(10000, 0);
  dfs(0, -1, adj, depth, 0);

  int max_depth = 0, end1 = -1, end2 = -1;
  for (int i = 0; i < 10000; i++)
    if (depth[i] > max_depth)
      max_depth = depth[i], end1 = i;
  
  max_depth = 0;
dfs(end1, -1, adj, depth2, 0);
  for (int i = 0; i < 10000; i++)
    if (depth2[i] > max_depth)
      max_depth = depth2[i], end2 = i;

  if (end1 > end2) swap(end1, end2);
  return {end1, end2};
}

vector<int> encode(int x, int len){
  vector<int> v(len);
  int num = x;
  for (int i = len - 1; i >= 0; i--){
    int d = num/pow5[i];
    v[i] = d;
    num -= d * pow5[i];
  }
  return v;
}

int decode(vector<int> x){
  int len = x.size();
  int ans = 0;
  for (int i = len - 1; i >= 0; i--){
    int d = x[i];
    ans += d * pow5[i];
  }
  return ans;
}

int encode12(int a, int b){
  for (int i = 0; i < 66; i++)
    if (map66[i].first == a && map66[i].second == b)
      return i;
  return -1;
}

pair<int, int> decode12(int x){
  return map66[x];
}

void pre(){
  pow5.resize(12, 1);
  for (int i = 1; i < 12; i++) pow5[i] = pow5[i-1] * 5;

  c1 = -1, c2 = -1;
  d1 = -1, d2 = -1;
  A = -1, B = -1, C = -1;

  map66.clear();
  for (int i = 0; i < 11; i++){
    for (int j = i + 1; j < 12; j++){
      map66.push_back({i, j});
    }
  }

  adj.resize(10000, vector<int>());
}

void one(int x, int y){
  if (d1 == x && d2 == y) C = 0;
  else if (d1 == x) C = 1;
  else C = 2;
}

void rone(int x, int y){
  if (C == 0) d1 = x, d2 = y;
  else if (C == 1) d1 = x, d2 = c;
  else d1 = y, d2 = c;
}

void two(int x, int y, int v){
  if (d2 != c){
    if (Q(x,v)) C = 0;
    if (Q(y,v)) C = 1;
  } else {
    if (d1 == x) C = 2;
    if (d1 == y) C = 3;
    if (d1 == v) C = 4;
  }
}

void rtwo(int x, int y, int v){
  if (C == 0) d1 = min(x, v), d2 = max(x, v);
  if (C == 1) d1 = min(y, v), d2 = max(y, v);
  if (C == 2) d1 = x, d2 = c;
  if (C == 3) d1 = y, d2 = c;
  if (C == 4) d1 = v, d2 = c;
}

int send_message(int N, int i, int Pi) {
  if (i == 1) pre();
  if (i <= 9981){
    upd;
    return 0;
  }

  if (i <= 9993){
    if (c1 == -1){
      int u, v;
      tie(u, v) = diameter();
      c1 = u, c2 = v;
    }
    upd;
    int V = 9999*c1 + c2;
    vector<int> enc = encode(V, 12);
    return enc[i - 9982];
  }

  if (i <= 9996){
    if (d1 == -1){
      int u, v;
      tie(u, v) = diameter();
      d1 = u, d2 = v;
    }
    upd;
    int V;
    if (c1 == d1 && c2 == d2) V = 124;
    else if (c1 == d1) V = 70 + d2 - 9982;
    else if (d1 == c2) V = 90 + d2 - 9982;
    else  V = encode12(d1, d2);
    vector<int> enc = encode(V, 3);
    if (i == 9996) c1 = d1, c2 = d2;
    return enc[i - 9994];
  }

  if (i == a) {
    upd;
    int u, v;
    tie(u, v) = diameter();

    if (R(c1, c2) || R(c1, p) || R(c1, q)) A = 0;
    if (R(c1, r)  || R(c1, a) || R(c2, p)) A = 1;
    if (R(c2, q)  || R(c2, r) || R(c2, a)) A = 2;
    if (R(p, q)   || R(p, r)  || R(p, a))  A = 3;
    if (R(q, r)   || R(q, a)  || R(r, a))  A = 4;
    return A;
  }

  if (i == b) {
    upd;
    int u, v;
    tie(u, v) = diameter();

    if (A == 0){
      if (R(c1, c2)) B = 0;
      if (R(c1, p))  B = 1;
      if (R(c1, q))  B = 2;
      if (R(c1, b) || R(c2, b)) B = 3;
      if (R(p, b)  || R(q, b))  B = 4;}
    if (A == 1){
      if (R(c1, r)) B = 0;
      if (R(c1, a) || R(c1, b)) B = 1;
      if (R(c2, p))  B = 2;
      if (R(c2, b) || R(r, b)) B = 3;
      if (R(p, b)  || R(a, b))  B = 4;}
    if (A == 2){
      if (R(c2, q)) B = 0;
      if (R(c2, r))  B = 1;
      if (R(c2, a))  B = 2;
      if (R(c2, b) || R(q, b)) B = 3;
      if (R(r, b)  || R(a, b))  B = 4;}
    if (A == 3){
      if (R(p, q)) B = 0;
      if (R(p, r))  B = 1;
      if (R(p, a))  B = 2;
      if (R(p, b) || R(q, b)) B = 3;
      if (R(r, b)  || R(a, b))  B = 4;}
    if (A == 4){
      if (R(q, r)) B = 0;
      if (R(q, a))  B = 1;
      if (R(r, a))  B = 2;
      if (R(q, b)) B = 3;
      if (R(r, b)  || R(a, b))  B = 4;}
    d1 = u, d2 = v;
    return B;
  }

  upd;
  int u = d1, v = d2;
  tie(d1, d2) = diameter();
  C = -1;
  if (A == 0){
      if (R(c1, c2)) one(c1, c2);
      if (R(c1, p))  one(c1, p);
      if (R(c1, q))  one(c1, q);
      if (R(c1, b) || R(c2, b)) two(c1, c2, b);
      if (R(p, b)  || R(q, b))  two(p, q, b);}
    if (A == 1){
      if (R(c1, r)) one(c1, r);
      if (R(c1, a) || R(c1, b)) two(a, b, c1);
      if (R(c2, p))  one(c2, p);
      if (R(c2, b) || R(r, b)) two(c2, r, b);
      if (R(p, b)  || R(a, b))  two(p, a, b);}
    if (A == 2){
      if (R(c2, q)) one(c2, q);
      if (R(c2, r))  one(c2, r);
      if (R(c2, a))  one(c2, a);
      if (R(c2, b) || R(q, b)) two(c2, q, b);
      if (R(r, b)  || R(a, b))  two(r, a, b);}
    if (A == 3){
      if (R(p, q)) one(p, q);
      if (R(p, r))  one(p, r);
      if (R(p, a))  one(p, a);
      if (R(p, b) || R(q, b)) two(p, q, b);
      if (R(r, b)  || R(a, b))  two(r, a, b);}
    if (A == 4){
      if (R(q, r)) one(q, r);
      if (R(q, a))  one(q, a);
      if (R(r, a))  one(r, a);
      if (R(q, b)) one(q, b);
      if (R(r, b)  || R(a, b))  two(r, a, b);}
  
  return C;
}

pair<int, int> longest_path(vector<int> S) {
  pre();

  vector<int> part1(12);
  for (int i = 9982; i <= 9993; i++) part1[i - 9982] = S[i];
  int V = decode(part1);
  int C1 = (V - V%c)/c, C2 = V%c;

  vector<int> part2(3);
  for (int i = p; i <= r; i++) part2[i - p] = S[i];
  V = decode(part2);

  if (V <= 67){
    int u, v;
    tie(u, v) = decode12(V);
    C1 = u + 9982, C2 = v + 9982;
  } else if (V < 90) {
    C2 = V + 9982 - 70;
  } else if (V < 120){
    C1 = V + 9982 - 90;
    swap(C1, C2);
  }

  A = S[a], B = S[b], C = S[c];
  d1 = -1, d2 = -1;
  if (A == 0){
    if (B == 0) rone(C1, C2);
    if (B == 1) rone(C1, p);
    if (B == 2) rone(C1, q);
    if (B == 3) rtwo(C1, C2, b);
    if (B == 4) rtwo(p, q, b);}
  if (A == 1){
    if (B == 0) rone(C1, r);
    if (B == 1) rtwo(a, b, C1);
    if (B == 2) rone(C2, p);
    if (B == 3) rtwo(C2, r, b);
    if (B == 4) rtwo(p, a, b);}
  if (A == 2){
    if (B == 0) rone(C2, q);
    if (B == 1) rone(C2, r);
    if (B == 2) rone(C2, a);
    if (B == 3) rtwo(C2, q, b);
    if (B == 4) rtwo(r, a, b);}
  if (A == 3){
    if (B == 0) rone(p, q);
    if (B == 1) rone(p, r);
    if (B == 2) rone(p, a);
    if (B == 3) rtwo(p, q, b);
    if (B == 4) rtwo(r, a, b);}
  if (A == 4){
    if (B == 0) rone(q, r);
    if (B == 1) rone(q, a);
    if (B == 2) rone(r, a);
    if (B == 3) rone(q, b);
    if (B == 4) rtwo(r, a, b);}
  return {d1, d2};
}

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