Submission #1257336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257336		nicolo_010	Migrations (IOI25_migrations)	C++20	30 / 100	35 ms	1432 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)

v<v<int>> adj;
int ans;
int mx;
int L, R;
int dis;

void dfs(int n, int d=0, int p=-1) {
  if (d > mx) {
    mx = d;
    ans = n;
  }
  for (auto x : adj[n]) {
    if (x == p) continue;
    dfs(x, d+1, n);
  }
}

int send_message(int N, int i, int Pi) {
  if (i == 1) {
    adj.resize(N);
  }
  adj[i].push_back(Pi);
  adj[Pi].push_back(i);
  if (i >= N-14) {
    mx=0;
    dfs(L);
    int aux = mx;
    mx=0;
    dfs(R);
    //return 4 = cambio R, 3 = cambio L, contrario bits R
    int b = i-(N-14);
    int k = R;
    rep(j, 0, b) {
      k /= 2;
    }
    if (aux > dis) {
      R = i;
      dis = aux;
      return 4;
    }
    else if (mx > dis) {
      L = i;
      dis = mx;
      return (k%2)+2;
    }
    else {
      return k%2;
    }
  }
  if (i == N-21) {
    dfs(0);
    L = ans;
    mx = 0;
    dfs(L);
    dis = mx;
    R = ans;
    return L%4;
  }
  if (i > N-21) {
    mx=0;
    dfs(L);
    int aux = mx;
    mx=0;
    dfs(R);
    if (aux > dis) {
      R = i;
      dis = aux;
    }
    else if (mx > dis) {
      L = i;
      dis = mx;
      return 4;
    }
    else {
      int b = (i-(N-21));
      int l = L;
      rep(j, 0, b) {
        l /= 4;
      }
      return l % 4;
    }
  } 
  else return 0;
}

std::pair<int, int> longest_path(std::vector<int> S) {
  int last4R = -1, last4L = -1;
  int N = S.size();
  int l = 0;
  v<int> pow(10);
  pow[0] = 1;
  rep(i, 1, 10) pow[i] = pow[i-1]*4;
  rep(i, N-21, N-14) {
    if (S[i] == 4) last4L = i;
    else {
      l += pow[i-(N-21)]*S[i];
    }
  }
  int r = 0;
  rep(i, N-14, N) {
    if (S[i] == 4) last4R = i;
    else if (S[i] >= 2) {
      last4L = i;
    }
    if (S[i] < 4) {
      if (S[i] == 1 || S[i] == 3) r += (1 << (i-(N-14)));
    }
    //cout << S[i] << " " << r << endl;
  }
  if (last4L != -1) l = last4L;
  if (last4R != -1) r = last4R;
  return {l, r};
}

Compilation message (stderr)

migrations.cpp: In function 'int send_message(int, int, int)':
migrations.cpp:76:11: warning: control reaches end of non-void function [-Wreturn-type]
   76 |       dis = aux;
      |       ~~~~^~~~~

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