Submission #981330

#TimeUsernameProblemLanguageResultExecution timeMemory
981330Jawad_Akbar_JJRainforest Jumps (APIO21_jumps)C++17
4 / 100
620 ms56720 KiB
#include "jumps.h" #include <iostream> #include <vector> #include <queue> using namespace std; const int N = 2e5 + 10, lg = 18; vector<int> nei[N], ch[N]; int lft[N]; int rgt[N]; int Mn[N]; int seen[N]; int idk[N]; int par[N]; bool sub1 = true; int st[N], en[N], hei[N],Cur = 1, Par[N][lg], dt[N][lg]; void dfs(int u,int p = 0){ hei[u] = hei[p] + 1; st[u] = Cur++; Par[u][0] = p; if (idk[u]) Par[u][0] = idk[u]; for (int i=1;i<=lg;i++) Par[u][i] = Par[Par[u][i-1]][i-1]; for (int i : ch[u]) dfs(i,u); en[u] = Cur++; } void init(int n,vector<int> h){ vector<int> v; for (int i=0;i<n;i++) sub1 &= (h[i] == i + 1); for (int i=0;i<n;i++) lft[i] = rgt[i] = -1; for (int i=0;i<n;i++){ while (v.size() > 0 and h[v.back()] < h[i]) rgt[v.back()] = i,v.pop_back(); v.push_back(i); } v.clear(); for (int i=n-1;i>=0;i--){ while (v.size() > 0 and h[v.back()] < h[i]) lft[v.back()] = i,v.pop_back(); v.push_back(i); } for (int i=0;i<n;i++){ if (lft[i] != -1) nei[i + 1].push_back(lft[i] + 1); if (rgt[i] != -1) nei[i + 1].push_back(rgt[i] + 1); } int rt; for (int i=0;i<n;i++){ if (lft[i] == -1 and rgt[i] == -1){ rt = i + 1; continue; } int to = rgt[i] + 1; if (rgt[i] == -1 or (lft[i] != -1 and h[lft[i]] < h[rgt[i]])) to = lft[i] + 1; ch[to].push_back(i + 1); par[i + 1] = to; if (rgt[i] == -1 or lft[i] == -1) continue; idk[i + 1] = lft[i] + rgt[i] + 2 - to; } dfs(rt); } int dist(int A,int C){ if ( !(st[C] <= st[A] and en[C] >= en[A]) ) return -1; int d = 1; for (int i=lg;i>=0;i--) if (hei[Par[A][i]] > hei[C]) d += (1<<i), A = Par[A][i]; return d; } int cur = 0; int minimum_jumps(int A, int B, int C, int D) { if (sub1) return C - B; if (A == B and C == D) return dist(A + 1,C + 1); cur++; queue<int> Q; for (int i=A+1;i<=B + 1;i++) Q.push(i),seen[i] = cur,Mn[i] = 0; while (!Q.empty()){ int u = Q.front(); if (u >= C+1 and u <= D+1) return Mn[u]; Q.pop(); for (int i : nei[u]) if (seen[i] != cur) Mn[i] = Mn[u] + 1,Q.push(i),seen[i] = cur; } return -1; }

Compilation message (stderr)

jumps.cpp: In function 'void dfs(int, int)':
jumps.cpp:32:19: warning: iteration 17 invokes undefined behavior [-Waggressive-loop-optimizations]
   32 |         Par[u][i] = Par[Par[u][i-1]][i-1];
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:31:19: note: within this loop
   31 |     for (int i=1;i<=lg;i++)
      |                  ~^~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:94:8: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |     dfs(rt);
      |     ~~~^~~~
#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...