Submission #1252453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252453		Jakub_Wozniak	Migrations (IOI25_migrations)	C++20	72.89 / 100	29 ms	2364 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10009;
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
int P[maxn] , jump[maxn] , dep[maxn] , jsiz[maxn] , dpth[maxn];
vector <int > s[maxn];
pii maxi[maxn][3];
pii aktp;
int aktlen = 0 ;

bool comp(pii p1 , pii p2)
{
  return p1 > p2;
}

void DFS(int v)
{
  dpth[v] = 0;
  maxi[v][0] = {0, v};
  maxi[v][1] = {0, v};
  maxi[v][2] = {0, v};
  for(auto p : s[v])
  {
    DFS(p);
    maxi[v][2] = {dpth[p]+1 , maxi[p][0].nd};
    sort(maxi[v] , maxi[v]+3 , comp);
    dpth[v] = max(dpth[v],dpth[p]+1);
  }

  int A = maxi[v][0].st + maxi[v][1].st;
  if(A > aktlen)
  {
    aktlen = A;
    aktp = {maxi[v][0].nd , maxi[v][1].nd};
  }
}

int find(int x, int w)
{
  while(w)
  {
    if(jsiz[x] <= w)
    {
      w -= jsiz[x];
      x = jump[x];
    }
    else
    {
      w--;
      x = P[x];
    }
  }
  return x;
}

int dis(int a ,int b)
{
  if(dep[a] > dep[b])swap(a,b);
  int az = a , bz = b;
  b = find(b , dep[b]-dep[a]);
  while(a != b)
  {
    if(jump[a] == jump[b])
    {
      a = P[a];
      b = P[b];
    }
    else
    {
      a = jump[a];
      b = jump[b];
    }
  }
  return dep[az]+dep[bz]-2*dep[a];
}

int send_message(int N, int i, int Pi) 
{
  if(i == 1)
  {
    for(int j = 0 ;j <= N ; j++)
    {
      P[j] = 0;
      s[j].clear();
      for(int k = 0; k < 3 ; k++)maxi[j][k].st = 0;
      for(int k = 0 ;k < 3 ; k++)maxi[j][k].nd = 0;
      jump[j] = 0;
      dep[j] = 0;
    }
  }

  P[i] = Pi;
  dep[i] = dep[Pi]+1;
  s[Pi].push_back(i);
  if(jsiz[Pi] == jsiz[jump[Pi]])
  {
    jsiz[i] = 2*jsiz[Pi]+1;
    jump[i] = jump[jump[Pi]];
  }
  else 
  {
    jsiz[i] = 1;
    jump[i] = Pi;
  }

  if(i == (N-1)-27)
  {
    aktp = {0,0}; aktlen = 0;
    DFS(0);
  }
  if(i >= (N-1)-27)
  {
    pii p1 = aktp , p2 = aktp;
    p1.st = i;
    p2.nd = i;
    int Z = 0;
    if(dis(p1.st , p1.nd) > dis(aktp.st , aktp.nd))
    {
      aktp = p1;
      Z = 1;
    }
    if(dis(p2.st , p2.nd) > dis(aktp.st , aktp.nd))
    {
      aktp = p2;
      Z = 2;
    }

    if(i < (N-1)-13)
    {
      int B = i-((N-1)-27);
      if(Z == 1)return 4;
      int V = 0;
      if(aktp.st&(1<<B))V = 1;
      if(Z == 2)V += 2;
      return V;
    }
    else
    {
      int B = i-((N-1)-13);
      if(Z == 2)return 4;
      int V = 0;
      if(aktp.nd&(1<<B))V = 1;
      if(Z == 1)V += 2;
      return V;
    }
  }
  return 0;
}

std::pair<int, int> longest_path(std::vector<int> S) 
{
  int N = S.size();
  int A = 0 , B = 0 ;
  bool czyzA = 0 , czyzB = 0;
  for(int i = N-1-27 ; i < N-1-13 ; i++)
  {
    if(S[i] == 4)
    {
      czyzA = 1;
      A = i;
      continue;
    }

    if(S[i] > 1)
    {
      czyzB = 1;
      B = i;
    }
    if(!czyzA)
    {
      if(S[i]%2)A += (1<<(i-(N-1-27)));
    }
  }
  for(int i = N-1-13 ; i <= N-1 ; i++)
  {
    if(S[i] == 4)
    {
      czyzB = 1;
      B = i;
      continue;
    }

    if(S[i] > 1)
    {
      czyzA = 1;
      A = i;
    }
    if(!czyzB)
    {
      if(S[i]%2)B += (1<<(i-(N-1-13)));
    }
  }

  return {A,B};
}


/*
45
0 1 2 2 3 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

*/

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