Submission #1262146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262146		madamadam3	Migrations (IOI25_migrations)	C++20	30 / 100	46 ms	1716 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;
}

string test_switch(vi codes) {
  vector<pi> switches; for (int i = 0; i < int(codes.size()); i++) if (codes[i] != 0) switches.push_back({i+2, codes[i] - 1}); 

  int A = 0, B = 1;
  int L = 1; 

  for (auto &el : switches) {
    int w = el.first;
    if (el.second) {
      (L == A ? B : A) = w;
    } else {
      (L == A ? A : B) = w;
    }
    L = w; 
  }

  return "(" + to_string(A) + "," + to_string(B) + ")";
}

vector<bool> bsearch(int x) { // record decision log of binary search to find x
  vector<bool> log;
  
  int lo = 0, hi = 10000;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (mid < x) {
      log.push_back(true);
      lo = mid + 1;
    } else {
      hi = mid;
      log.push_back(false);
    }
  }

  return log;
}

vvi adj;
pi fr;
int diam = 0,  prev_change = 0, cpos = 0;
vector<int> change_types;
vector<int> diam_history;

int x = 0;
int seen2 = -1;
int send_message(int n, int i, int Pi) {
  if (i <= 1) adj.assign(n+1, vi());
  x = n - 28;

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

  if (i < x) return 0;
  int step = i - x;
  if (seen2 != -1) step--;

  if (step == 0) {fr = furthest_pair(n, adj); diam = dist_between(n, fr.first, fr.second, adj); prev_change = fr.second;}

  int ans = 0;
  if (step < 14) ans = min(1, fr.first & (1 << step));
  else ans = min(1, fr.second & (1 << (step - 14)));

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

  if (cdiam == diam) {
    return ans;
  } else if (dist_between(n, i, prev_change, adj) == cdiam) {
    diam = cdiam;
    prev_change = i;
    return ans + 2;
  } else {
    prev_change = i;
    diam = cdiam;
    seen2 = step;
    return 4;
    // return ans + 4;
  }

  return ans;
}

pi longest_path(vi S) {
  int n = S.size();
  int x = n - 28;
  int count2 = 0; for (int i = x; i < n; i++) if (S[i] == 4) count2++;

  int u = 0, v = 0;
  vector<pi> switches;

  if (count2 == 0) {
    for (int i = x; i < x + 14; i++) {
      if (S[i] >= 4) {
        switches.push_back({i, 0});
        u |= (S[i] - 4) << (i - x);
      } else if (S[i] >= 2) {
        switches.push_back({i, 1});
        u |= (S[i] - 2) << (i - x);
      } else {
        u |= S[i] << (i - x);
      }
    }

    for (int i = x + 14; i < n; i++) {
      if (S[i] >= 4) {
        switches.push_back({i, 0});
        v |= (S[i] - 4) << (i - x - 14);
      } else if (S[i] >= 2) {
        switches.push_back({i, 1});
        v |= (S[i] - 2) << (i - x - 14);
      } else {
        v |= S[i] << (i - x - 14);
      }
    }
  } else if (count2 == 1) {
    int si = 0, idx = x;
    while (si < 14) {
      if (S[idx] == 4) {idx++; continue;}

      u |= S[idx] << (si);
      idx++; si++;
    }

    for (int i = x; i < n; i++) {
      if (S[i] == 4) switches.push_back({i, 0});
      else if (S[i] >= 2) switches.push_back({i, 1});
    }
  } else {
    for (int i = x; i < n; i++) {
      if (S[i] == 4) switches.push_back({i, 0});
      else if (S[i] >= 2) switches.push_back({i, 1});
    }
  }

  int A = u, B = v;
  int L = v; 

  for (auto &el : switches) {
    int w = el.first;
    if (el.second) {
      (L == A ? B : A) = w;
    } else {
      (L == A ? A : B) = w;
    }
    L = w; 
  }

  return {A, B}; 
}

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