oj.uz

Submission #698154

# Submission time Handle Problem Language Result Execution time Memory
698154 2023-02-12T14:37:32 Z perohero Speedrun (RMI21_speedrun) C++17
100 / 100
 120 ms 876 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 756 KB Output is correct
2 Correct 119 ms 712 KB Output is correct
3 Correct 99 ms 672 KB Output is correct
4 Correct 109 ms 684 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 812 KB Output is correct
2 Correct 86 ms 672 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 720 KB Output is correct
2 Correct 100 ms 700 KB Output is correct
3 Correct 104 ms 712 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 676 KB Output is correct
2 Correct 105 ms 832 KB Output is correct
3 Correct 120 ms 716 KB Output is correct
4 Correct 96 ms 692 KB Output is correct
5 Correct 105 ms 876 KB Output is correct
6 Correct 92 ms 676 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 676 KB Output is correct
2 Correct 106 ms 712 KB Output is correct
3 Correct 74 ms 668 KB Output is correct
4 Correct 107 ms 720 KB Output is correct
5 Correct 89 ms 672 KB Output is correct
6 Correct 98 ms 672 KB Output is correct
7 Correct 113 ms 716 KB Output is correct