Submission #1298178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298178		rxlfd314	Migrations (IOI25_migrations)	C++20	58 / 100	1763 ms	1728 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 10005;
vt<int> adj[mxN];
int U, V = 1, best = 1, UU, VV = 1;

int find_dist(const int i, const int p, const int target, const int d) {
  if (i == target)
    return d;
  int ret = 0;
  for (const auto &j : adj[i])
    if (j != p)
      ret = max(ret, find_dist(j, i, target, d + 1));
  return ret;
}

int send_message(const int N, const int i, const int Pi) {
  adj[Pi].push_back(i);
  adj[i].push_back(Pi);
  const int iu = find_dist(i, -1, U, 0);
  const int iv = find_dist(i, -1, V, 0);
  if (i < N - 28) {
    if (max(iu, iv) > best) {
      best = max(iu, iv);
      if (iv > iu)
        UU = U = V;
      VV = V = i;
    }
    return 0;
  }
  int ret = (i < N - 14 ? UU : VV) >> i - N + (i < N - 14 ? 28 : 14) & 1;
  if (max(iu, iv) <= best)
    ret |= 4;
  else {
    best = max(iu, iv);
    if (iv > iu)
      U = V;
    else
      ret |= 2;
    V = i;
  }
  return ret;
}
  
pair<int, int> longest_path(const vt<int> S) {
  const int N = size(S);
  U = 0, V = 0;
  FOR(i, N - 28, N - 15)
    U |= (S[i] & 1) << i - N + 28;
  FOR(i, N - 14, N - 1)
    V |= (S[i] & 1) << i - N + 14;
  FOR(i, N - 28, N - 1) {
    if (S[i] & 4)
      continue;
    if (~S[i] & 2)
      U = V;
    V = i;
  }
  return {U, V};
}

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