Submission #1226100

#TimeUsernameProblemLanguageResultExecution timeMemory
1226100Jer즐거운 행로 (APIO20_fun)C++20
0 / 100
0 ms324 KiB
#include "fun.h" #include <bits/stdc++.h> #include <vector> using namespace std; const int MAXN = 100005; bool used[MAXN]; int m[MAXN]; int n; int dfs(int i, int d){ if (2 * i + 1 >= n) {m[i] = d; return d;} m[i] = dfs(2 * i + 1, d + 1); if (2 * i + 2 < n) dfs(2 * i + 2, d + 1); return m[i]; } int find_deepest(int i){ if (2 * i + 1 >= n) {used[i] = true, m[i]--; return i;} int res = m[i]; if (!used[2 * i + 1] and !used[2 * i + 2]){ if (m[2 * i + 1] >= m[2 * i + 2]) res = find_deepest(2 * i + 1); else res = find_deepest(2 * i + 2); m[i] = max(m[2 * i + 1], m[2 * i + 2]); return res; } if (used[2 * i + 1] and !used[2 * i + 2]){ res = find_deepest(2 * i + 2); m[i] = max(m[2 * i + 1], m[2 * i + 2]); return res; } if (!used[2 * i + 1] and used[2 * i + 2]) { res = find_deepest(2 * i + 1); m[i] = max(m[2 * i + 1], m[2 * i + 2]); return res; } used[i] = true, m[i]--; return i; } std::vector<int> createFunTour(int N, int Q) { if (n == 2) return {0, 1}; n = N; vector<int> res; dfs(0, 0); int curr = 0, r, l; for (int i = 0; i <= n; i += 2){ r = -1; if (used[2 * curr + 2]) r = curr, curr = 2 * curr + 1; if (r == -1) r = find_deepest(2 * curr + 2); l = (used[2 * curr + 1]) ? curr : find_deepest(curr); if (l == curr) res.push_back(r); else res.push_back(l), res.push_back(r); } res.push_back(curr); return res; }
#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...