제출 #1258500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258500		ogkostya	이주 (IOI25_migrations)	C++20	63.58 / 100	41 ms	1472 KiB

migrations

#include "migrations.h"
#include <queue>
#include <cstdio>
#include <map>
#include <stdexcept>
#include <algorithm>

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

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

std::map<int, int> lmap;
std::map<int, int> rmap;

void ClearMap(std::map<int, int> &m, int i)
{
  m.clear();
  m[i] = 0;
}
void AddMap(std::map<int, int> &m, int pi, int i)
{
  auto it = m.find(pi);
  if (it != m.end())
  {
    m[i] = 1 + it->second;
  }
}
int GetMap(std::map<int, int> &m)
{
  int max = -1;
  int index = -1;
  for (const auto &pair : m)
  {
    if (max < pair.second)
    {
      max = pair.second;
      index = pair.first;
    }
    else if (max == pair.second)
    {
      if (index < pair.first)
        index = pair.first;
    }
  }
  return index;
}

int left = -1, right = -1;

void pack4(int to, int p[])
{
}
void pack5(int to, int p[], int count, int w)
{
  for (int i = count - 1; i >= 0; i--)
  {
    p[i] = to % 5;
    to /= 5;
  }
  if (to > 0)
    throw std::runtime_error("A runtime error occurred.");
}
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;

bool FirstNearer(int point, int first, int second)
{
  d1[point] = -1;
  dfs(point, point, d1);
  return d1[first] < d1[second];
}

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;

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

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

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);

  AddMap(lmap, Pi, i);
  AddMap(rmap, Pi, i);

  if (i == N - 1)
  {
    auto p = Step(GetMap(lmap));
    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(GetMap(rmap));
    if (FirstNearer(left, p.first, p.second) || FirstNearer(right, p.second, p.first))
    {
      p = std::make_pair(p.second, p.first);
    }
    if (p.second == left)
    {
      return 0;
    }
    else
    {
      left = p.second;
      ClearMap(lmap, left);
      return i + 1 - left;
    }
  }
  else if (i == N - 3)
  {
    auto p = Step(GetMap(lmap));
    if (FirstNearer(right, p.first, p.second) || FirstNearer(left, p.second, p.first))
    {
      p = std::make_pair(p.second, p.first);
    }
    if (p.second == right)
    {
      return 0;
    }
    else
    {
      right = p.second;
      ClearMap(rmap, right);
      return i + 1 - right;
    }
  }
  else if (i >= N - 5)
  {
    if (i == N - 5)
    {
      auto p = Step(GetMap(rmap));
      if (p.second == left)
      {
        pack5(0, p1, 2, 4);
      }
      else
      {
        left = p.second;
        ClearMap(lmap, left);
        pack5(i + 1 - left, p1, 2, 4);
      }
    }
    return p1[i - (N - 5)];
  }
  else if (i >= N - 7)
  {
    if (i == N - 7)
    {
      auto p = Step(GetMap(lmap));
      if (p.second == right)
      {
        pack5(0, p2, 2, 3);
      }
      else
      {
        right = p.second;
        ClearMap(rmap, right);
        pack5(i + 1 - right, p2, 2, 3);
      }
    }
    return p2[i - (N - 7)];
  }
  else if (i >= N - 13)
  {
    if (i == N - 13)
    {
      auto p = Step(GetMap(rmap));
      // if (p.second == left)
      // {
      //   pack5(0, p3, 6, 2);
      // }
      // else
      {
        left = p.second;
        ClearMap(lmap, left);
        pack5(left, p3, 6, 2);
      }
    }
    return p3[i - (N - 13)];
  }
  else if (i >= N - 19)
  {
    if (i == N - 19)
    {
      auto p = Step(GetMap(lmap));
      right = p.second;
      ClearMap(rmap, right);
      pack5(right, p4, 6, 1);
    }
    return p4[i - (N - 19)];
  }
  else if (i >= N - 25)
  {
    if (i == N - 25)
    {
      auto p = Step(i);
      left = std::max(p.first, p.second);
      ClearMap(lmap, left);
      pack5(left, p5, 6, 0);
    }
    return p5[i - (N - 25)];
  }

  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;
        l = i;
      }
      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);
    }
    if (i == n - 25 && l == -1)
    {
      l = 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: 30 / 30
• Subtask 2: 33.5833 / 70