Submission #1070888

#TimeUsernameProblemLanguageResultExecution timeMemory
1070888nhuang685Speedrun (RMI21_speedrun)C++17
0 / 100
1 ms600 KiB
#include "speedrun.h" #include <bits/stdc++.h> constexpr int LG = 10; void dfs( int node, std::vector<int> &par, std::vector<int> &id, std::vector<int> &t, const std::vector<std::vector<int>> &adj ) { t.push_back(node); id[node] = static_cast<int>(t.size()) - 1; for (int i : adj[node]) { if (i == par[node]) { continue; } par[i] = node; dfs(i, par, id, t, adj); } } void assignHints(int /*subtask*/, int N, int A[], int B[]) { const int n = N; std::vector<std::vector<int>> adj(n + 1); for (int i = 1; i < n; ++i) { adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]); } std::vector<int> par(n + 1, -1), id(n + 1, -1), t; dfs(1, par, id, t, adj); setHintLen(2 * LG); for (int i = 1; i <= n; ++i) { if (par[i] != -1) { for (int j = 0; j < LG; ++j) { setHint(i, j, ((1 << j) & par[i]) != 0); } } if (id[i] != n - 1) { int nxt = t[id[i] + 1]; for (int j = 0; j < LG; ++j) { setHint(i, j + LG, ((1 << j) & nxt) != 0); } } } } int get_par() { int ans = 0; for (int j = 0; j < LG; ++j) { if (getHint(j)) { ans |= 1 << j; } } return ans; } int get_nxt() { int ans = 0; for (int j = 0; j < LG; ++j) { if (getHint(j + LG)) { ans |= 1 << j; } } return ans; } void speedrun(int /*subtask*/, int N, int start) { const int n = N; int node = start; while (node != 1) { node = get_par(); bool b = goTo(node); assert(b); } std::stack<int, std::vector<int>> st; st.push(1); for (int i = 1; i < n; ++i) { int nxt = get_nxt(); while (!st.empty()) { if (goTo(nxt)) { st.push(nxt); break; } st.pop(); bool b = goTo(st.top()); assert(b); } } }
#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...