Submission #698154

#	Time	Username	Problem	Language	Result	Execution time	Memory
698154		tvladm2009	Speedrun (RMI21_speedrun)	C++17	100 / 100	120 ms	876 KiB

speedrun

#include <bits/stdc++.h>
#include "speedrun.h"

using namespace std;

typedef long long ll;
const int N = (int) 1e3 + 7;
int masks[N];
vector<int> g[N], t;

void dfs(int u, int p = -1) {
  t.push_back(u);
  for (auto &v : g[u]) {
    if (v != p) {
      masks[v] = u;
      dfs(v, u);
    }
  }
}

int lg2 = 0;

void assignHints(int subtask, int N, int A[], int B[]) {
  lg2 = 0;
  while ((1 << (lg2 + 1)) <= N) {
    lg2++;
  }
  lg2++;
  setHintLen(2 * lg2);
  for (int i = 1; i < N; i++) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  dfs(1);
  for (int i = 0; i < N; i++) {
    int u = t[i];
    for (int b = 0; b < lg2; b++) {
      if (masks[u] & (1 << b)) {
        setHint(u, b + 1, 1);
      }
      if (i != N - 1 && (t[i + 1] & (1 << b))) {
        setHint(u, lg2 + 1 + b, 1);
      }
    }
  }
}

int get(int u, int len) {
  int result = 0;
  for (int b = 0; b < len; b++) {
    if (getHint(b + 1)) {
      result += (1 << b);
    }
  }
  return result;
}

int get2(int u, int len) {
  int result = 0;
  for (int b = 0; b < len; b++) {
    if (getHint(len + b + 1)) {
      result += (1 << b);
    }
  }
  return result;
}

void speedrun(int subtask, int N, int start) {
  int len = getLength() / 2, node = start;
  while (node != 1) {
    int par = get(node, len);
    goTo(par);
    node = par;
  }
  int node2 = get2(node, len);
  while (node2 > 0) {
    if (!goTo(node2)) {
      goTo(get(node, len));
    } else {
      node = node2;
      node2 = get2(node, len);
    }
  }
}

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40