oj.uz

Submission #730344

# Submission time Handle Problem Language Result Execution time Memory
730344 2023-04-25T17:43:04 Z Andrei_Calota Speedrun (RMI21_speedrun) C++14
100 / 100
 141 ms 836 KB 
#include <bits/stdc++.h>
#include<speedrun.h>

using namespace std;

const int NMAX = 1e3;
const int BITS = 20, HALF = 10;
const int ROOT = 1, NONE = 0;

int par[1 + NMAX];
vector<int> tree[1 + NMAX];
int lastNode; int nextPreoder[1 + NMAX];

void DFSassign (int root, int p) {
    par[root] = p;
    nextPreoder[lastNode] = root; lastNode = root;
    for (int node : tree[root])
       if (node != p)
          DFSassign (node, root);
}

void assignHints (int substask, int N, int A[], int B[]) {
   setHintLen (BITS);
   for (int i = 1; i < N; i ++) {
      tree[A[i]].push_back (B[i]);
      tree[B[i]].push_back (A[i]);
   }
   DFSassign (ROOT, NONE);
   for (int node = 1; node <= N; node ++)
      for (int bit = 0; bit < HALF; bit ++)
         if (par[node] & (1 << bit))
           setHint (node, bit + 1, true);

   for (int node = 1; node <= N; node ++)
      for (int bit = HALF; bit < BITS; bit ++)
         if (nextPreoder[node] & (1 << (bit - HALF)))
           setHint (node, bit + 1, true);
}



int getPar () {
   int p = 0;
   for (int bit = 0; bit < HALF; bit ++)
      if (getHint (bit + 1) == true)
        p = p + (1 << bit);
    return p;
}
int getNextPreoder () {
   int preord = 0;
   for (int bit = HALF; bit < BITS; bit ++)
      if (getHint (bit + 1) == true)
        preord = preord + (1 << (bit - HALF));
   return preord;
}

void speedrun (int subtask, int N, int start) {
   getLength ();

   while (getPar () > 0)
      goTo (getPar ());


   while (getNextPreoder () != NONE) {
      int target = getNextPreoder ();
      while (!goTo (target))
         goTo (getPar ());
   }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 712 KB Output is correct
2 Correct 115 ms 724 KB Output is correct
3 Correct 104 ms 724 KB Output is correct
4 Correct 102 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 792 KB Output is correct
2 Correct 106 ms 672 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 684 KB Output is correct
2 Correct 88 ms 812 KB Output is correct
3 Correct 82 ms 672 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 748 KB Output is correct
2 Correct 138 ms 728 KB Output is correct
3 Correct 131 ms 684 KB Output is correct
4 Correct 129 ms 672 KB Output is correct
5 Correct 113 ms 676 KB Output is correct
6 Correct 103 ms 672 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 672 KB Output is correct
2 Correct 114 ms 836 KB Output is correct
3 Correct 114 ms 716 KB Output is correct
4 Correct 113 ms 712 KB Output is correct
5 Correct 129 ms 688 KB Output is correct
6 Correct 128 ms 700 KB Output is correct
7 Correct 110 ms 712 KB Output is correct