Submission #1252179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252179		bynix	Migrations (IOI25_migrations)	C++20	0 / 100	29 ms	1204 KiB

migrations

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

vector<vector<int>> adj123;
vector<int> pow5123;

int c1123, c2123;
int d123, d223;

#define upd123 {adj123[i].push_back(Pi); adj123[Pi].push_back(i);}

#define P123(k123, l123) (u == k123 && v == l123)
#define Q123(k123, l123) ((d123 == k123 && d223 == l123) || (d123 == l123 && d223 == k123))

const int p123 = 9994, q123 = 9995, r123 = 9996;
const int a123 = 9997, b123 = 9998, c123 = 9999;

int A123, B123, C123;

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

pair<int, int> diameter123(){
  vector<int> depth(10000, 0), depth2(10000, 0);
  dfs123(0, -1, adj123, depth, 0);

  int max_depth = 0, end1, end2;
  for (int i = 0; i < 10000; i++)
    if (depth[i] > max_depth)
      max_depth = depth[i], end1 = i;
  
  max_depth = 0;
  dfs123(end1, -1, adj123, 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> encode123(int x, int len){
  vector<int> v(len);
  int num = x;
  for (int i = len - 1; i >= 0; i--){
    int d = num/pow5123[i];
    v[i] = d;
    num -= d * pow5123[i];
  }
  return v;
}

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

vector<pair<int, int>> m123;
int encode12(int a, int b){
  for (int i = 0; i < 66; i++)
    if (m123[i].first == a && m123[i].second == b)
      return i;
}

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

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

  c1123 = -1, c2123 = -1;
  d123 = -1, d223 = -1;

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

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

void one123(int x, int y){
  if (d123 == x && d223 == y) C123 = 0;
  else if (d123 == x) C123 = 1;
  else C123 = 2;
}

void rone123(int x, int y){
  if (C123 == 0) d123 = x, d223 = y;
  else if (C123 == 1) d123 = x, d223 = c123;
  else d123 = y, d223 = c123;
}

void two123(int x, int y, int v){
  if (d223 != c123){
    if (Q123(x,v)) C123 = 0;
    if (Q123(y,v)) C123 = 1;
  } else {
    if (d123 == x) C123 = 2;
    if (d123 == y) C123 = 3;
    if (d123 == v) C123 = 4;
  }
}

void rtwo123(int x, int y, int v){
  if (C123 == 0) d123 = min(x, v), d223 = max(x, v);
  if (C123 == 1) d123 = min(y, v), d223 = max(y, v);
  if (C123 == 2) d123 = x, d223 = c123;
  if (C123 == 3) d123 = y, d223 = c123;
  if (C123 == 4) d123 = v, d223 = c123;
}

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

  if (i <= 9993){
    if (c1123 == -1){
      auto [u, v] = diameter123();
      c1123 = u, c2123 = v;
    }
    upd123;
    int V = 9999*c1123 + c2123;
    vector<int> enc = encode123(V, 12);
    return enc[i - 9982];
  }

  if (i <= 9996){
    if (d123 == -1){
      auto [u, v] = diameter123();
      d123 = u, d223 = v;
    }
    upd123;
    int V;
    if (c1123 == d123 && c2123 == d223) V = 124;
    else if (c1123 == d123) V = 70 + d223 - 9982;
    else if (d123 == c2123) V = 90 + d223 - 9982;
    else  V = encode12(d123, d223);
    vector<int> enc = encode123(V, 3);
    if (i == 9996) c1123 = d123, c2123 = d223;
    return enc[i - 9994];
  }

  if (i == a123) {
    upd123;
    auto [u, v] = diameter123();

    if (P123(c1123, c2123) || P123(c1123, p123) || P123(c1123, q123)) A123 = 0;
    if (P123(c1123, r123)  || P123(c1123, a123) || P123(c2123, p123)) A123 = 1;
    if (P123(c2123, q123)  || P123(c2123, r123) || P123(c2123, a123)) A123 = 2;
    if (P123(p123, q123)   || P123(p123, r123)  || P123(p123, a123))  A123 = 3;
    if (P123(q123, r123)   || P123(q123, a123)  || P123(r123, a123))  A123 = 4;
    return A123;
  }

  if (i == b123) {
    upd123;
    auto [u, v] = diameter123();

    if (A123 == 0){
      if (P123(c1123, c2123)) B123 = 0;
      if (P123(c1123, p123))  B123 = 1;
      if (P123(c1123, q123))  B123 = 2;
      if (P123(c1123, b123) || P123(c2123, b123)) B123 = 3;
      if (P123(p123, b123)  || P123(q123, b123))  B123 = 4;}
    if (A123 == 1){
      if (P123(c1123, r123)) B123 = 0;
      if (P123(c1123, a123) || P123(c1123, b123)) B123 = 1;
      if (P123(c2123, p123))  B123 = 2;
      if (P123(c2123, b123) || P123(r123, b123)) B123 = 3;
      if (P123(p123, b123)  || P123(a123, b123))  B123 = 4;}
    if (A123 == 2){
      if (P123(c2123, q123)) B123 = 0;
      if (P123(c2123, r123))  B123 = 1;
      if (P123(c2123, a123))  B123 = 2;
      if (P123(c2123, b123) || P123(q123, b123)) B123 = 3;
      if (P123(r123, b123)  || P123(a123, b123))  B123 = 4;}
    if (A123 == 3){
      if (P123(p123, q123)) B123 = 0;
      if (P123(p123, r123))  B123 = 1;
      if (P123(p123, a123))  B123 = 2;
      if (P123(p123, b123) || P123(q123, b123)) B123 = 3;
      if (P123(r123, b123)  || P123(a123, b123))  B123 = 4;}
    if (A123 == 4){
      if (P123(q123, r123)) B123 = 0;
      if (P123(q123, a123))  B123 = 1;
      if (P123(r123, a123))  B123 = 2;
      if (P123(q123, b123)) B123 = 3;
      if (P123(r123, b123)  || P123(a123, b123))  B123 = 4;}
    d123 = u, d223 = v;
    return B123;
  }

  upd123;
  int u = d123, v = d223;
  tie(d123, d223) = diameter123();
  if (A123 == 0){
      if (P123(c1123, c2123)) one123(c1123, c2123);
      if (P123(c1123, p123))  one123(c1123, p123);
      if (P123(c1123, q123))  one123(c1123, q123);
      if (P123(c1123, b123) || P123(c2123, b123)) two123(c1123, c2123, b123);
      if (P123(p123, b123)  || P123(q123, b123))  two123(p123, q123, b123);}
    if (A123 == 1){
      if (P123(c1123, r123)) one123(c1123, r123);
      if (P123(c1123, a123) || P123(c1123, b123)) two123(a123, b123, c1123);
      if (P123(c2123, p123))  one123(c2123, p123);
      if (P123(c2123, b123) || P123(r123, b123)) two123(c2123, r123, b123);
      if (P123(p123, b123)  || P123(a123, b123))  two123(p123, a123, b123);}
    if (A123 == 2){
      if (P123(c2123, q123)) one123(c2123, q123);
      if (P123(c2123, r123))  one123(c2123, r123);
      if (P123(c2123, a123))  one123(c2123, a123);
      if (P123(c2123, b123) || P123(q123, b123)) two123(c2123, q123, b123);
      if (P123(r123, b123)  || P123(a123, b123))  two123(r123, a123, b123);}
    if (A123 == 3){
      if (P123(p123, q123)) one123(p123, q123);
      if (P123(p123, r123))  one123(p123, r123);
      if (P123(p123, a123))  one123(p123, a123);
      if (P123(p123, b123) || P123(q123, b123)) two123(p123, q123, b123);
      if (P123(r123, b123)  || P123(a123, b123))  two123(r123, a123, b123);}
    if (A123 == 4){
      if (P123(q123, r123)) one123(q123, r123);
      if (P123(q123, a123))  one123(q123, a123);
      if (P123(r123, a123))  one123(r123, a123);
      if (P123(q123, b123)) one123(q123, b123);
      if (P123(r123, b123)  || P123(a123, b123))  two123(r123, a123, b123);}
  
  return C123;
}

pair<int, int> longest_path(vector<int> S) {
  vector<int> part1(12);
  for (int i = 9982; i <= 9993; i++) part1[i - 9982] = S[i];
  int V = decode123(part1);
  int c1123 = (V - V%c123)/c123, c2123 = V%c123;

  vector<int> part2(3);
  for (int i = p123; i <= r123; i++) part2[i - p123] = S[i];
  V = decode123(part2);

  if (V <= 67){
    auto [u, v] = decode12(V);
    c1123 = u + 9982, c2123 = v + 9982;
  } else if (V < 90) {
    c2123 = V + 9982 - 70;
  } else if (V < 120){
    c1123 = V + 9982 - 90;
    swap(c1123, c2123);
  }

  A123 = S[a123], B123 = S[b123], C123 = S[c123];
  if (A123 == 0){
    if (B123 == 0) rone123(c1123, c2123);
    if (B123 == 1) rone123(c1123, p123);
    if (B123 == 2) rone123(c1123, q123);
    if (B123 == 3) rtwo123(c1123, c2123, b123);
    if (B123 == 4) rtwo123(p123, q123, b123);}
  if (A123 == 1){
    if (B123 == 0) rone123(c1123, r123);
    if (B123 == 1) rtwo123(a123, b123, c1123);
    if (B123 == 2) rone123(c2123, p123);
    if (B123 == 3) rtwo123(c2123, r123, b123);
    if (B123 == 4) rtwo123(p123, a123, b123);}
  if (A123 == 2){
    if (B123 == 0) rone123(c2123, q123);
    if (B123 == 1) rone123(c2123, r123);
    if (B123 == 2) rone123(c2123, a123);
    if (B123 == 3) rtwo123(c2123, q123, b123);
    if (B123 == 4) rtwo123(r123, a123, b123);}
  if (A123 == 3){
    if (B123 == 0) rone123(p123, q123);
    if (B123 == 1) rone123(p123, r123);
    if (B123 == 2) rone123(p123, a123);
    if (B123 == 3) rtwo123(p123, q123, b123);
    if (B123 == 4) rtwo123(r123, a123, b123);}
  if (A123 == 4){
    if (B123 == 0) rone123(q123, r123);
    if (B123 == 1) rone123(q123, a123);
    if (B123 == 2) rone123(r123, a123);
    if (B123 == 3) rone123(q123, b123);
    if (B123 == 4) rtwo123(r123, a123, b123);}
  return {d123, d223};
}

Compilation message (stderr)

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

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