제출 #1258419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258419		ogkostya	Migrations (IOI25_migrations)	C++20	0 / 100	32 ms	1472 KiB

migrations

#include "migrations.h"
#include <queue>
#include <cstdio>

std::vector<std::vector<int>> nn;

int p1[32];
int p2[32];
int p3[32];
int p4[32];
int d1[10001];
int d2[10001];
int d3[10001];

int left = -1, right = -1;

void pack4(int to, int p[])
{
}
void pack5(int to, int p[], int count)
{
  for (int i = count - 1; i >= 0; i--)
  {
    p[i] = to % 5;
    to /= 5;
  }
}
int unpack5(std::vector<int> &s, int index, int count)
{
  int ans = 0;
  for (int i = index, k = 0; k < count; i++, k++)
  {
    ans *= 5;
    ans += s[i];
  }
  return ans;
}

void dfs(int to, int from, int d[])
{
  d[to] = 1 + d[from];
  for (int j : nn[to])
  {
    if (j == from)
      continue;
    dfs(j, to, d);
  }
}

int n;

std::pair<int, int> Step(int i)
{
  d1[i] = -1;
  dfs(i, i, d1);
  int m1 = 0;
  for (int j = 0; j <= n; j++)
    if (d1[m1] <= d1[j])
      m1 = j;

  d2[m1] = -1;
  dfs(m1, m1, d2);
  int m2 = 0;
  for (int j = 0; j <= n; j++)
    if (d2[m2] <= d2[j])
      m2 = j;

  //printf("%d %d\n", m2, m1);
  return std::make_pair(m2, m1);
}

int send_message(int N, int i, int Pi)
{
  n = i;
  if (nn.size() == 0)
  {
    nn = std::vector<std::vector<int>>(N, std::vector<int>());
  }
  nn[i].push_back(Pi);
  nn[Pi].push_back(i);

  if (i == N - 1)
  {
    auto p = Step(left);
    if (p.first == i)
    {
      if (p.second == i - 1)
      {
        return 3;
      }
      else
      {
        return 4;
      }
    }
    else
    {
      if (p.second == i)
      {
        return 1;
      }
      else if (p.second == i - 1)
      {
        return 2;
      }
    }
  }
  else if (i == N - 2)
  {
    auto p = Step(right);
    if (p.second == left)
    {
      return 0;
    }
    else
    {
      left = p.second;
      return i + 1 - left;
    }
  }
  else if (i == N - 3)
  {
    auto p = Step(left);
    if (p.second == right)
    {
      return 0;
    }
    else
    {
      right = p.second;
      return i + 1 - right;
    }
  }
  else if (i >= N - 5)
  {
    if (i == N - 5)
    {
      auto p = Step(right);
      if (p.second == left)
      {
        pack5(0, p1, 2);
      }
      else
      {
        left = p.second;
        pack5(i + 1 - left, p1, 2);
      }
    }
    return p1[i - (N - 5)];
  }
  else if (i >= N - 7)
  {
    if (i == N - 7)
    {
      auto p = Step(left);
      if (p.second == right)
      {
        pack5(0, p2, 2);
      }
      else
      {
        right = p.second;
        pack5(i + 1 - right, p2, 2);
      }
    }
    return p2[i - (N - 7)];
  }
  else if (i >= N - 13)
  {
    if (i == N - 13)
    {
      auto p = Step(right);
      left = p.second;
      pack5(left, p3, 6);
    }
    return p3[i - (N - 13)];
  }
  else if (i >= N - 19)
  {
    if (i == N - 19)
    {
      auto p = Step(i);
      left = p.first;
      right = p.second;
      pack5(right, p4, 6);
    }
    return p4[i - (N - 19)];
  }

  return 0;
}

std::pair<int, int> longest_path(std::vector<int> S)
{
  n = S.size();
  int l = -1, r = -1;

  for (int i = n - 1; i >= 0; i--)
  {
    if (i == n - 1)
    {
      if (S[i] == 4)
      {
        l = i;
      }
      else if (S[i] == 3)
      {
        r = i - 1;
      }
      else if (S[i] == 2)
      {
        r = i - 1;
      }
      else if (S[i] == 1)
      {
        r = i;
      }
    }
    if (i == n - 2 && l == -1)
    {
      if (S[i] != 0)
      {
        l = i + 1 - S[i];
      }
    }
    if (i == n - 3 && r == -1)
    {
      if (S[i] != 0)
      {
        r = i + 1 - S[i];
      }
    }
    if (i == n - 5 && l == -1)
    {
      int p = unpack5(S, i, 2);
      if (p != 0)
      {
        l = i + 1 - p;
      }
    }
    if (i == n - 7 && r == -1)
    {
      int p = unpack5(S, i, 2);
      if (p != 0)
      {
        r = i + 1 - p;
      }
    }
    if (i == n - 13 && l == -1)
    {
      l = unpack5(S, i, 6);
    }
    if (i == n - 19 && r == -1)
    {
      r = unpack5(S, i, 6);
    }

    //printf("%d %d %d\n", i, l, r);

    if (l != -1 && r != -1)
      return {l, r};
  }
  return {0, 1};
}

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