Submission #645300

#	Time	Username	Problem	Language	Result	Execution time	Memory
645300		Alex_tz307	Speedrun (RMI21_speedrun)	C++17	100 / 100	135 ms	832 KiB

speedrun

/* Input format:
 *
 * N -- number of nodes
 * a1 b1 -- edge 1
 * ...
 * a(N-1) b(N-1) -- edge N - 1
 * x -- start node
 */

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

using namespace std;

/*
static map<int, map<int, bool>> mp;
static int length = -1;
static int queries = 0;
static bool length_set = false;
static int current_node = 0;
static set<int> viz;
static map<int, set<int>> neighbours;

void setHintLen(int l) {
    if (length_set) {
        cerr << "Cannot call setHintLen twice" << endl;
        exit(0);
    }
    length = l;
    length_set = true;
}

void setHint(int i, int j, bool b) {
    if (!length_set) {
        cerr << "Must call setHintLen before setHint" << endl;
        exit(0);
    }
    mp[i][j] = b;
}

int getLength() { return length; }

bool getHint(int j) { return mp[current_node][j]; }

bool goTo(int x) {
    if (neighbours[current_node].find(x) == end(neighbours[current_node])) {
        ++queries;
        return false;
    } else {
        viz.insert(current_node = x);
        return true;
    }
}
*/

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[]) { /* your solution here */
  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) { /* your solution here */
  int lg = 0;
  while (1 << (lg + 1) <= N) {
    lg += 1;
  }
  lg += 1;
  int l = getLength();
  int 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);
    }
  }
}

/*
int main() {
    int N;
    cin >> N;

    int a[N], b[N];
    for (int i = 1; i < N; ++i) {
        cin >> a[i] >> b[i];
        neighbours[a[i]].insert(b[i]);
        neighbours[b[i]].insert(a[i]);
    }

    assignHints(1, N, a, b);

    if (!length_set) {
        cerr << "Must call setHintLen at least once" << endl;
        exit(0);
    }

    cin >> current_node;
    viz.insert(current_node);

    speedrun(1, N, current_node);

    if ((int)viz.size() < N) {
        cerr << "Haven't seen all nodes" << endl;
        exit(0);
    }

    cerr << "OK; " << queries << " incorrect goto's" << endl;
    return 0;
}
*/

Compilation message (stderr)

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:122:7: warning: unused variable 'l' [-Wunused-variable]
  122 |   int l = getLength();
      |       ^

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