Submission #673067

#TimeUsernameProblemLanguageResultExecution timeMemory
673067VaheRainforest Jumps (APIO21_jumps)C++17
60 / 100
4038 ms68488 KiB
#include "jumps.h" #include <iostream> #include <algorithm> #include <vector> #include <stack> using namespace std; int n, a, b, c, d; vector<int> h, pge, nge, dp, l, r; vector<vector<int>> gp; vector<bool> vis1, vis2; bool arajitest = 1; vector<vector<int>> up1, up2; vector<int> pge_(vector<int> v) { vector<int> tmp(v.size()); stack<int> s; s.push(0); tmp[0] = -1; for (int i = 1; i < v.size(); i++) { while (!s.empty() && v[s.top()] < v[i]) s.pop(); tmp[i] = (s.empty() ? -1 : s.top()); s.push(i); } return tmp; } vector<int> nge_(vector<int> v) { stack<int> s; vector<int> tmp(v.size(), -1); for (int i = 0; i < n; i++) { while (!s.empty() && v[s.top()] < v[i]) tmp[s.top()] = i, s.pop(); s.push(i); } return tmp; } void dfs(int u) { if (u >= c && u <= d) { dp[u] = 0; return; } if (dp[u] != 2e9) return; if (gp[u].size() > 0) dfs(gp[u][0]); if (gp[u].size() > 1) dfs(gp[u][1]); int x = (gp[u].size() > 0 ? dp[gp[u][0]] : 2e9); int y = (gp[u].size() > 1 ? dp[gp[u][1]] : 2e9); dp[u] = min(x, y) + 1; } void make1(int u) { if (vis1[u]) return; vis1[u] = 1; int x = l[u]; int y = r[u]; if (x == -1) swap(x, y); if (y == -1 && x != -1 && !vis1[x]) { make1(x); } else if (x != -1 && y != -1) { if (h[x] > h[y]) swap(x, y); if (!vis1[x]) make1(x); } up1[u][0] = x; for (int i = 1; i < 20; i++) up1[u][i] = up1[u][i - 1] != -1 ? up1[up1[u][i - 1]][i - 1] : -1; } void make2(int u) { if (vis2[u]) return; vis2[u] = 1; int x = l[u]; int y = r[u]; if (x == -1) swap(x, y); if (y == -1 && x != -1 && !vis2[x]) make2(x); else if (x != -1 && y != -1) { if (h[x] < h[y]) swap(x, y); if (!vis2[x]) make2(x); } up2[u][0] = x; for (int i = 1; i < 20; i++) up2[u][i] = up2[u][i - 1] != -1 ? up2[up2[u][i - 1]][i - 1] : -1; } void init(int N, vector<int> H) { n = N, h = H, l = pge_(H), r = nge_(H); gp = vector<vector<int>>(n); for (int i = 0; i < n; i++) { if (l[i] != -1) gp[i].push_back(l[i]); if (r[i] != -1) gp[i].push_back(r[i]); } for (int i = 0; i < n; i++) if (H[i] != i + 1) arajitest = 0; if (a == b && c == d) { up1 = up2 = vector<vector<int>>(n, vector<int>(20, -1)); vis1 = vis2 = vector<bool>(n); for (int i = 0; i < n; i++) { if (!vis1[i]) make1(i); if (!vis2[i]) make2(i); } } } int minimum_jumps(int A, int B, int C, int D) { a = A, b = B, c = C, d = D; if (arajitest) return C - B; else if (a == b && c == d) { int G = A, len = 0; for (int i = 19; i >= 0; i--) { if (up2[G][i] != -1 && h[up2[G][i]] <= h[C]) G = up2[G][i], len += (1 << i); } if (G == C) return len; for (int i = 19; i >= 0; i--) { if (up1[G][i] != -1 && h[up1[G][i]] <= h[C]) G = up1[G][i], len += (1 << i); } return G == C ? len : -1; } else { dp = vector<int>(n, 2e9); int mn = 2e9; for (int i = a; i <= b; i++) dfs(i), mn = min(mn, dp[i]); return (mn >= 2e9 ? -1 : mn); } }

Compilation message (stderr)

jumps.cpp: In function 'std::vector<int> pge_(std::vector<int>)':
jumps.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 1; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...