Submission #645302

#TimeUsernameProblemLanguageResultExecution timeMemory
645302Alex_tz307Speedrun (RMI21_speedrun)C++17
0 / 100
87 ms700 KiB
#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(), 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); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...