Submission #1155013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155013		fryingduc	Speedrun (RMI21_speedrun)	C++20	100 / 100	56 ms	512 KiB

speedrun

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

using namespace std;

const int maxn = 1005;
int n, tin[maxn], et[maxn];
int timer;
int par[maxn];
vector<int> g[maxn];

void dfs(int u, int prev) {
  tin[u] = ++timer;
  et[timer] = u;
  for (auto v:g[u]) {
    if (v == prev) continue;
    par[v] = u;
    dfs(v, u);
  }
}

void assignHints(int subtask, int N, int A[], int B[]) {
  n = N;
  for (int i = 1; i <= n; ++i) {
    g[i].clear();
  }
  for (int i = 1; i < n; ++i) {
    int u = A[i], v = B[i];
    g[u].push_back(v);
    g[v].push_back(u);
  }
  timer = par[1] = 0;
  dfs(1, 0);
  setHintLen(20);
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 10; ++j) {
      setHint(i, j + 1, (par[i] >> j & 1));
    }
    int t = tin[i];
    if (t < n) {
      t = et[t + 1];
      for (int j = 0; j < 10; ++j) {
        setHint(i, j + 1 + 10, (t >> j & 1));
      }
    }
  }
}

int getp() {
  int p = 0;
  for (int i = 0; i < 10; ++i) {
    if (getHint(i + 1)) {
      p |= (1 << i);
    }
  }
  return p;
}

int gets() {
  int p = 0;
  for (int i = 0; i < 10; ++i) {
    if (getHint(i + 1 + 10)) {
      p |= (1 << i);
    }
  }
  return p;
}

void speedrun(int subtask, int N, int start) {
  n = N;
  vector<bool> vis(n + 1);
  vis[start] = 1;
  while (true) {
    int p = getp();
    if (!p) break;
    goTo(p);
  }
  while (true) {
    int nxt = gets();
    if (!nxt) {
      break;
    }
    while (!goTo(nxt)) {
      goTo(getp());
    }
  }
}

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