제출 #1282298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282298		joelgun14	이주 (IOI25_migrations)	C++20	30 / 100	31 ms	1072 KiB

migrations

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

const int N = 10000;

int x = 0, y = 1;
bool done_x = 0, done_y = 0;
int par[16][N + 5];
int depth[N + 5];

// calculate distance between two nodes
int dist(int x, int y) {
  if (depth[x] < depth[y]) {
    swap(x, y);
  }

  int res = 0;
  for (int i = 15; i >= 0; --i) {
    if (par[i][x] != -1 && depth[par[i][x]] >= depth[y]) {
      x = par[i][x];
      res += 1 << i;
    }
  }

  if (x == y) {
    return res;
  }

  for (int i = 15; i >= 0; --i) {
    if (par[i][x] != par[i][y]) {
      x = par[i][x];
      y = par[i][y];
      res += 1 << (i + 1);
    }
  }

  return res + 2;
}

int send_message(int N, int nd, int pr) {
  // special init case
  if (nd == 1) {
    memset(par, -1, sizeof(par));
    return 0;
  }
  
  // calc binlift and depth
  depth[nd] = depth[pr] + 1;
  par[0][nd] = pr;
  for (int i = 1; i < 16; ++i) {
    if (par[i - 1][nd] != -1) {
      par[i][nd] = par[i - 1][par[i - 1][nd]];
    }
  }

  // check dist(x, nd), dist(y, nd), see if x or y changed
  bool cx = 0, cy = 0;
  if (dist(x, nd) > dist(x, y)) {
    cy = 1;
    y = nd;
  } else if (dist(y, nd) > dist(x, y)) {
    cx = 1;
    x = nd;
  }

  if (nd >= N - 24 && nd < N - 16) {
    // communicate x phase
    if (done_x) {
      return cx;
    } else if (cx) {
      done_x = 1;
      return 0;
    } else {
      int num = nd - (N - 24); // the num-th message we send for x, starting from 0
      int cur = (x >> (2 * num)) & 3;
      return cur + 1;
    }
  }  else if (nd >= N - 16) {
    // communicate y phase
    if (done_y) {
      return cx ? 2 : cy;
    } else if (cy) {
      done_y = 1;
      return 0;
    } else {
      int num = nd - (N - 16); // the num-th message we send for y, starting from 0
      int cur = (y >> num) & 1;
      return (cur + 1) + (cx ? 2 : 0);
    }
  }

  // default
  return 0;
}

std::pair<int, int> longest_path(std::vector<int> S) {
  int val_x = 0, val_y = 0, shift = 0;
  bool done_x = 0, done_y = 0;

  // communicate x phase
  for (int i = N - 24; i < N - 16; ++i) {
    if (done_x) {
      val_x = S[i] == 1 ? i : val_x;
    } else {
      if (S[i] == 0) {
        val_x = i, done_x = i;
      } else {
        val_x += (S[i] - 1) << shift;
        shift += 2;
      }
    }
  }

  shift = 0;
  // communicate y phase
  for (int i = N - 16; i < N; ++i) {
    if (done_y) {
      if (S[i] == 2) val_x = i;
      else if (S[i] == 1) val_y = i;
    } else {
      if (S[i] == 0) {
        val_y = i, done_y = i;
      } else {
        val_y += (S[i] - 1) << shift;
        ++shift;
        val_x = S[i] > 2 ? i : val_x;
      }
    }
  }

  return {val_x, val_y};
}

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