제출 #533875

#제출 시각아이디문제언어결과실행 시간메모리
533875hollwo_pelw밀림 점프 (APIO21_jumps)C++17
27 / 100
1220 ms33712 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int big_jmp[18][N], sml_jmp[18][N]; int h[N], ljmp[N], rjmp[N]; void init(int n, vector<int> a) { a.insert(a.begin(), n + 1); // to 1-based static int st[N]; for (int i = 1, top = 0; i <= n; i++) { while (top && a[st[top]] < a[i]) rjmp[st[top --]] = i; st[++ top] = i; } for (int i = n, top = 0; i >= 1; i--) { while (top && a[st[top]] < a[i]) ljmp[st[top --]] = i; st[++ top] = i; } for (int i = 1; i <= n; i++) { big_jmp[0][i] = a[rjmp[i]] > a[ljmp[i]] ? rjmp[i] : ljmp[i]; sml_jmp[0][i] = a[rjmp[i]] < a[ljmp[i]] ? rjmp[i] : ljmp[i]; } for (int i = 1; i < 18; i++) for (int j = 1; j <= n; j++) { big_jmp[i][j] = big_jmp[i - 1][big_jmp[i - 1][j]]; sml_jmp[i][j] = sml_jmp[i - 1][sml_jmp[i - 1][j]]; } vector<int> ord(n); for (int i = 1; i <= n; i++) ord[n - a[i]] = i; for (auto u : ord) h[u] = h[sml_jmp[0][u]] + 1; } inline int lca(int u, int v) { if (h[u] > h[v]) swap(u, v); for (int i = 18; i --; ) if (h[v] - h[u] >> i & 1) v = sml_jmp[i][v]; if (u == v) return u; for (int i = 18; i --; ) if (sml_jmp[i][u] ^ sml_jmp[i][v]) u = sml_jmp[i][u], v = sml_jmp[i][v]; return sml_jmp[0][u]; } int minimum_jumps(int a, int b, int c, int d) { ++ a, ++ b, ++ c, ++ d; // to 1-based int u = lca(a, b), v = lca(c, d), res = 0; { int possible = lca(u, v); if (possible != v) return -1; } for (int i = 18; i --; ) if (h[big_jmp[i][u]] >= h[v]) { res += 1 << i; u = big_jmp[i][u]; } if (c <= u && u <= d) return res; for (int i = 18; i --; ) if (h[sml_jmp[i][u]] >= h[v] && sml_jmp[i][u] < c) { res += 1 << i; u = sml_jmp[i][u]; } return res + 1; }

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'int lca(int, int)':
jumps.cpp:50:12: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   50 |   if (h[v] - h[u] >> i & 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...