oj.uz

Submission #498665

# Submission time Handle Problem Language Result Execution time Memory
498665 2021-12-26T04:58:06 Z model_code Speedrun (RMI21_speedrun) C++17
100 / 100
 146 ms 912 KB 
// speedrun_100_tinca.cpp
#include <bits/stdc++.h>
#include "speedrun.h"

const int MAX_N = 1000;
int father[1+MAX_N], euler[1+MAX_N], lastId;
std::vector<int> graph[1+MAX_N];

void dfs(int node, int dfsfather = 0) {
  father[node] = dfsfather;
  euler[lastId++] = node;
  
  for (auto it: graph[node])
    if (it != dfsfather) {
      dfs(it, node);
    }
}

void setInteger(int node, int id, int value) {
  int offset = id * 10 + 1;
  for (int b = 0; b < 10; ++b) {
    if ((1 << b) & value)
      setHint(node, offset + b, true);
  }
}

int readInteger(int id) {
  int offset = id * 10 + 1;
  int value = 0;
  for (int b = 0; b < 10; ++b) {
    value = value ^ (getHint(offset + b) << b);
  }
  return value;
}

void assignHints(int subtask, int N, int A[], int B[]) {
  setHintLen(20);
  for (int i = 1; i <= N - 1; ++i) {
    graph[A[i]].push_back(B[i]);
    graph[B[i]].push_back(A[i]);
  }
  dfs(1);
  
  for (int i = 0; i < N; ++i) {
    setInteger(i + 1, 0, father[i + 1]);
    setInteger(euler[i], 1, euler[(i + 1) % N]);
  }
}

void speedrun(int subtask, int N, int start) {
  int node = start;
  do {
    int target = readInteger(1);
    while (!goTo(target)) {
      node = readInteger(0);
      goTo(node);
    }
    node = target;
  } while (node != start);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 688 KB Output is correct
2 Correct 146 ms 912 KB Output is correct
3 Correct 143 ms 768 KB Output is correct
4 Correct 137 ms 780 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 700 KB Output is correct
2 Correct 111 ms 716 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 724 KB Output is correct
2 Correct 102 ms 676 KB Output is correct
3 Correct 131 ms 660 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 804 KB Output is correct
2 Correct 82 ms 704 KB Output is correct
3 Correct 107 ms 776 KB Output is correct
4 Correct 120 ms 720 KB Output is correct
5 Correct 130 ms 704 KB Output is correct
6 Correct 121 ms 828 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 704 KB Output is correct
2 Correct 124 ms 720 KB Output is correct
3 Correct 126 ms 848 KB Output is correct
4 Correct 124 ms 708 KB Output is correct
5 Correct 115 ms 772 KB Output is correct
6 Correct 138 ms 696 KB Output is correct
7 Correct 89 ms 716 KB Output is correct