Submission #1252571

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

migrations

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

vector<vector<int>> adj;
vector<int> pow5;

int c1, c2;
int d1, d2;
int globalA, globalB;

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) {
  vector<pair<int, int>> m;
  for (int i = 0; i < 11; i++) {
    for (int j = i + 1; j < 12; j++) {
      m.push_back({i, j});
    }
  }
  for (int i = 0; i < 66; i++)
    if (m[i].first == a && m[i].second == b)
      return i;
  return -1;
}

pair<int, int> decode12(int x) {
  vector<pair<int, int>> m;
  for (int i = 0; i < 11; i++) {
    for (int j = i + 1; j < 12; j++) {
      m.push_back({i, j});
    }
  }

  return m[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;

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

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

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

int send_message(int N, int i, int Pi) {
  if (i == 1)
    pre();
  if (i <= 9981) {
    adj[i].push_back(Pi);
    adj[Pi].push_back(i);
    return 0;
  }

  if (i <= 9993) {
    if (c1 == -1) {
      int u, v;
      tie(u, v) = diameter();
      c1 = u, c2 = v;
    }
    adj[i].push_back(Pi);
    adj[Pi].push_back(i);
    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;
    }
    adj[i].push_back(Pi);
    adj[Pi].push_back(i);
    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 == 9997) {
    adj[i].push_back(Pi);
    adj[Pi].push_back(i);
    int u, v;
    tie(u, v) = diameter();
    int A;
    if ((u == c1 && v == c2) || (u == c1 && v == 9994) ||
        (u == c1 && v == 9995))
      A = 0;
    else if ((u == c1 && v == 9996) || (u == c1 && v == 9997) ||
             (u == c2 && v == 9994))
      A = 1;
    else if ((u == c2 && v == 9995) || (u == c2 && v == 9996) ||
             (u == c2 && v == 9997))
      A = 2;
    else if ((u == 9994 && v == 9995) || (u == 9994 && v == 9996) ||
             (u == 9994 && v == 9997))
      A = 3;
    else
      A = 4;
    globalA = A;
    return A;
  }

  if (i == 9998) {
    adj[i].push_back(Pi);
    adj[Pi].push_back(i);
    int u, v;
    tie(u, v) = diameter();

    int A = globalA, B;
    if (A == 0) {
      if ((u == c1 && v == c2))
        B = 0;
      else if ((u == c1 && v == 9994))
        B = 1;
      else if ((u == c1 && v == 9995))
        B = 2;
      else if ((u == c1 && v == 9998) || (u == c2 && v == 9998))
        B = 3;
      else
        B = 4;
    } else if (A == 1) {
      if ((u == c1 && v == 9996))
        B = 0;
      else if ((u == c1 && v == 9997) || (u == c1 && v == 9998))
        B = 1;
      else if ((u == c2 && v == 9994))
        B = 2;
      else if ((u == c2 && v == 9998) || (u == 9996 && v == 9998))
        B = 3;
      else
        B = 4;
    } else if (A == 2) {
      if ((u == c2 && v == 9995))
        B = 0;
      else if ((u == c2 && v == 9996))
        B = 1;
      else if ((u == c2 && v == 9997))
        B = 2;
      else if ((u == c2 && v == 9998) || (u == 9995 && v == 9998))
        B = 3;
      else
        B = 4;
    } else if (A == 3) {
      if ((u == 9994 && v == 9995))
        B = 0;
      else if ((u == 9994 && v == 9996))
        B = 1;
      else if ((u == 9994 && v == 9997))
        B = 2;
      else if ((u == 9994 && v == 9998) || (u == 9995 && v == 9998))
        B = 3;
      else
        B = 4;
    } else {
      if ((u == 9995 && v == 9996))
        B = 0;
      else if ((u == 9995 && v == 9997))
        B = 1;
      else if ((u == 9996 && v == 9997))
        B = 2;
      else if ((u == 9995 && v == 9998))
        B = 3;
      else
        B = 4;
    }
    d1 = u, d2 = v;
    globalB = B;
    return B;
  }

  adj[i].push_back(Pi);
  adj[Pi].push_back(i);
  int u = d1, v = d2;
  tie(d1, d2) = diameter();
  int A = globalA, C;
  if (A == 0) {
    if ((u == c1 && v == c2))
      one(c1, c2, d1, d2, C);
    else if ((u == c1 && v == 9994))
      one(c1, 9994, d1, d2, C);
    else if ((u == c1 && v == 9995))
      one(c1, 9995, d1, d2, C);
    else if ((u == c1 && v == 9998) || (u == c2 && v == 9998))
      two(c1, c2, 9998, d1, d2, C);
    else
      two(9994, 9995, 9998, d1, d2, C);
  } else if (A == 1) {
    if ((u == c1 && v == 9996))
      one(c1, 9996, d1, d2, C);
    else if ((u == c1 && v == 9997) || (u == c1 && v == 9998))
      two(9997, 9998, c1, d1, d2, C);
    else if ((u == c2 && v == 9994))
      one(c2, 9994, d1, d2, C);
    else if ((u == c2 && v == 9998) || (u == 9996 && v == 9998))
      two(c2, 9996, 9998, d1, d2, C);
    else
      two(9994, 9997, 9998, d1, d2, C);
  } else if (A == 2) {
    if ((u == c2 && v == 9995))
      one(c2, 9995, d1, d2, C);
    else if ((u == c2 && v == 9996))
      one(c2, 9996, d1, d2, C);
    else if ((u == c2 && v == 9997))
      one(c2, 9997, d1, d2, C);
    else if ((u == c2 && v == 9998) || (u == 9995 && v == 9998))
      two(c2, 9995, 9998, d1, d2, C);
    else
      two(9996, 9997, 9998, d1, d2, C);
  } else if (A == 3) {
    if ((u == 9994 && v == 9995))
      one(9994, 9995, d1, d2, C);
    else if ((u == 9994 && v == 9996))
      one(9994, 9996, d1, d2, C);
    else if ((u == 9994 && v == 9997))
      one(9994, 9997, d1, d2, C);
    else if ((u == 9994 && v == 9998) || (u == 9995 && v == 9998))
      two(9994, 9995, 9998, d1, d2, C);
    else
      two(9996, 9997, 9998, d1, d2, C);
  } else {
    if ((u == 9995 && v == 9996))
      one(9995, 9996, d1, d2, C);
    else if ((u == 9995 && v == 9997))
      one(9995, 9997, d1, d2, C);
    else if ((u == 9996 && v == 9997))
      one(9996, 9997, d1, d2, C);
    else if ((u == 9995 && v == 9998))
      one(9995, 9998, d1, d2, C);
    else
      two(9996, 9997, 9998, d1, d2, C);
  }

  return C;
}

// end of part 1 //

pair<int, int> rone(int x, int y, int C) {
  if (C == 0)
    return {x, y};
  else if (C == 1)
    return {x, 9999};
  else
    return {y, 9999};
}

pair<int, int> rtwo(int x, int y, int v, int C) {
  if (C == 0)
    return {min(x, v), max(x, v)};
  else if (C == 1)
    return {min(y, v), max(y, v)};
  else if (C == 2)
    return {x, 9999};
  else if (C == 3)
    return {y, 9999};
  else
    return {v, 9999};
}

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 % 9999)) / 9999, C2 = V % 9999;

  vector<int> part2(3);
  for (int i = 9994; i <= 9996; i++)
    part2[i - 9994] = 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);
  } else {
  }

  int A = S[9997], B = S[9998], C = S[9999];
  
  if (A == 0) {
    if (B == 0)
      return rone(C1, C2, C);
    else if (B == 1)
      return rone(C1, 9994, C);
    else if (B == 2)
      return rone(C1, 9995, C);
    else if (B == 3)
      return rtwo(C1, C2, 9998, C);
    else
      return rtwo(9994, 9995, 9998, C);
  } else if (A == 1) {
    if (B == 0)
      return rone(C1, 9996, C);
    else if (B == 1)
      return rtwo(9997, 9998, C1, C);
    else if (B == 2)
      return rone(C2, 9994, C);
    else if (B == 3)
      return rtwo(C2, 9996, 9998, C);
    else
      return rtwo(9994, 9997, 9998, C);
  } else if (A == 2) {
    if (B == 0)
      return rone(C2, 9995, C);
    else if (B == 1)
      return rone(C2, 9996, C);
    else if (B == 2)
      return rone(C2, 9997, C);
    else if (B == 3)
      return rtwo(C2, 9995, 9998, C);
    else
      return rtwo(9996, 9997, 9998, C);
  } else if (A == 3) {
    if (B == 0)
      return rone(9994, 9995, C);
    else if (B == 1)
      return rone(9994, 9996, C);
    else if (B == 2)
      return rone(9994, 9997, C);
    else if (B == 3)
      return rtwo(9994, 9995, 9998, C);
    else
      return rtwo(9996, 9997, 9998, C);
  } else {
    if (B == 0)
      return rone(9995, 9996, C);
    else if (B == 1)
      return rone(9995, 9997, C);
    else if (B == 2)
      return rone(9996, 9997, C);
    else if (B == 3)
      return rone(9995, 9998, C);
    else
      return rtwo(9996, 9997, 9998, C);
  }
}

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