제출 #984289

#제출 시각아이디문제언어결과실행 시간메모리
984289Marcus밀림 점프 (APIO21_jumps)C++17
0 / 100
4033 ms41916 KiB
#include "jumps.h" #include <vector> #include <bits/stdc++.h> using namespace std; int n; vector<int> h; const int INF = 2e6; vector<vector<int>> adj(2e5); int k; vector<vector<int>> st1; vector<vector<int>> st2; void init(int N, std::vector<int> H) { n = N; for (auto u: H) {h.push_back(u);} h.shrink_to_fit(); for (int i=0; i<n; i++) { for (int j=i; j<n; j++) { if (h[i] < h[j]) {adj[i].push_back(j); break;}; } for (int j=i; j>=0; j--) { if (h[i] < h[j]) {adj[i].push_back(j); break;}; } } k = (int)__lg(n); st1.resize(k+1); for (auto &u: st1) {u.resize(n, -1);} st2.resize(k+1); for (auto &u: st2) {u.resize(n, -1);} for (int j = 0; j < n; j++) { if (adj[j].size() == 2) { int x = adj[j][0]; int y = adj[j][1]; if (h[x] > h[y]) {st1[0][j] = x; st2[0][j] = y;} else {st1[0][j] = y; st2[0][j] = x;} } else if (adj[j].size() == 1) { int x = adj[j][0]; st2[0][j] = x; } } for (int i = 1; i <= k; i++) { for (int j = 0; j < n; j++) { if (st1[i-1][j] != -1) st1[i][j] = st1[i-1][st1[i-1][j]]; if (st2[i-1][j] != -1) st2[i][j] = st2[i-1][st2[i-1][j]]; } } } int minimum_jumps(int A, int B, int C, int D) { int answer = 0; int point = A; for (int i = k; i >= 0; i--) { if (st1[i][point] != -1 && h[st1[i][point]] <= h[C]) { answer += (int)pow(2, i); point = st1[i][point]; } if (point == C) return answer; } for (int i = k; i >= 0; i--) { if (st2[i][point] != -1 && h[st2[i][point]] <= h[C]) { answer += (int)pow(2, i); point = st2[i][point]; } if (point == C) return answer; } return -1; }
#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...