Submission #1070936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070936		nhuang685	Speedrun (RMI21_speedrun)	C++17	0 / 100	1 ms	600 KiB

speedrun

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

constexpr int LG = 10;

void dfs(
  int node,
  std::vector<int> &par,
  std::vector<int> &id,
  std::vector<int> &t,
  const std::vector<std::vector<int>> &adj
) {
  t.push_back(node);
  id[node] = static_cast<int>(t.size()) - 1;
  for (int i : adj[node]) {
    if (i == par[node]) {
      continue;
    }
    par[i] = node;
    dfs(i, par, id, t, adj);
  }
}

void assignHints(int /*subtask*/, int N, int A[], int B[]) {
  if (N <= 20) {
    setHintLen(1);
    return;
  }
  const int n = N;
  std::vector<std::vector<int>> adj(n + 1);
  for (int i = 1; i < n; ++i) {
    adj[A[i]].push_back(B[i]);
    adj[B[i]].push_back(A[i]);
  }
  std::vector<int> par(n + 1, -1), id(n + 1, -1), t;
  dfs(1, par, id, t, adj);

  setHintLen(2 * LG);
  for (int i = 1; i <= n; ++i) {
    if (par[i] != -1) {
      for (int j = 0; j < LG; ++j) {
        setHint(i, j, ((1 << j) & par[i]) != 0);
      }
    }
    if (id[i] != n - 1) {
      int nxt = t[id[i] + 1];
      for (int j = 0; j < LG; ++j) {
        setHint(i, j + LG, ((1 << j) & nxt) != 0);
      }
    }
  }
}

int get_par() {
  int ans = 0;
  for (int j = 0; j < LG; ++j) {
    if (getHint(j)) {
      ans |= 1 << j;
    }
  }
  return ans;
}

int get_nxt() {
  int ans = 0;
  for (int j = 0; j < LG; ++j) {
    if (getHint(j + LG)) {
      ans |= 1 << j;
    }
  }
  return ans;
}

void dfs_small(int node, int par, int n) {
  for (int i = 1; i <= n; ++i) {
    if (i != par && goTo(i)) {
      dfs_small(i, node, n);
    }
  }
  if (par != -1) {
    bool b = goTo(par);
    assert(b);
  }
}

void speedrun(int /*subtask*/, int N, int start) {
  if (N <= 20) {
    dfs_small(start, -1, N);
    return;
  }
  const int n = N;
  int node = start;
  while (node != 1) {
    node = get_par();
    bool b = goTo(node);
    assert(b);
  }

  std::stack<int, std::vector<int>> st;
  st.push(1);
  for (int i = 1; i < n; ++i) {
    int nxt = get_nxt();
    while (!st.empty()) {
      if (goTo(nxt)) {
        st.push(nxt);
        break;
      }
      st.pop();
      bool b = goTo(st.top());
      assert(b);
    }
  }
}

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