oj.uz

Submission #645303

# Submission time Handle Problem Language Result Execution time Memory
645303 2022-09-26T17:23:25 Z Alex_tz307 Speedrun (RMI21_speedrun) C++17
100 / 100
 122 ms 840 KB 
#include <bits/stdc++.h>
#include "speedrun.h"
 
using namespace std;
 
const int kN = 1e3;
int par[1 + kN];
vector<int> g[1 + kN];
vector<int> order;
 
void dfs(int u) {
  order.emplace_back(u);
  for (int v : g[u]) {
    if (v != par[u]) {
      par[v] = u;
      dfs(v);
    }
  }
}
 
void assignHints(int subtask, int N, int A[], int B[]) { 
  int lg = 0;
  while (1 << (lg + 1) <= N) {
    lg += 1;
  }
  lg += 1;
  setHintLen(2 * lg);
  for (int i = 1; i < N; ++i) {
    g[A[i]].emplace_back(B[i]);
    g[B[i]].emplace_back(A[i]);
  }
  dfs(1);
  for (int i = 0; i < N; ++i) {
    int v = order[i];
    for (int bit = 0; bit < lg; ++bit) {
      if (par[v] & (1 << bit)) {
        setHint(v, 1 + bit, true);
      }
      if (i < N - 1 && (order[i + 1] & (1 << bit))) {
        setHint(v, lg + 1 + bit, true);
      }
    }
  }
}
 
int getPar(int x, int lg) {
  int res = 0;
  for (int bit = 0; bit < lg; ++bit) {
    if (getHint(bit + 1)) {
      res += (1 << bit);
    }
  }
  return res;
}
 
int getNext(int x, int lg) {
  int res = 0;
  for (int bit = 0; bit < lg; ++bit) {
    if (getHint(lg + 1 + bit)) {
      res += (1 << bit);
    }
  }
  return res;
}
 
void speedrun(int subtask, int N, int start) {
  int lg = getLength() / 2, curr = start;
  while (curr != 1) {
    int p = getPar(curr, lg);
    goTo(p);
    curr = p;
  }
  int nxt = getNext(curr, lg);
  while (nxt) {
    if (!goTo(nxt)) {
      goTo(getPar(curr, lg));
    } else {
      curr = nxt;
      nxt = getNext(curr, lg);
    }
  }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 696 KB Output is correct
2 Correct 95 ms 720 KB Output is correct
3 Correct 117 ms 700 KB Output is correct
4 Correct 112 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 672 KB Output is correct
2 Correct 102 ms 712 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 740 KB Output is correct
2 Correct 81 ms 692 KB Output is correct
3 Correct 87 ms 672 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 696 KB Output is correct
2 Correct 105 ms 672 KB Output is correct
3 Correct 112 ms 796 KB Output is correct
4 Correct 94 ms 700 KB Output is correct
5 Correct 122 ms 712 KB Output is correct
6 Correct 82 ms 840 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 672 KB Output is correct
2 Correct 111 ms 716 KB Output is correct
3 Correct 98 ms 676 KB Output is correct
4 Correct 82 ms 676 KB Output is correct
5 Correct 115 ms 672 KB Output is correct
6 Correct 101 ms 708 KB Output is correct
7 Correct 100 ms 724 KB Output is correct