제출 #744469

#제출 시각아이디문제언어결과실행 시간메모리
744469speedyArda밀림 점프 (APIO21_jumps)C++14
25 / 100
1101 ms199416 KiB
#include "jumps.h" #include <vector> #include "bits/stdc++.h" using namespace std; bool sub1 = true; const int MAXN = 2e5+5, SMALL = 2e3+5, BIT = 18; vector< vector<int> > adj(MAXN), revadj(MAXN); vector< vector<int> > dist(SMALL, vector<int>(SMALL, 1e9)); int sparse[SMALL][12][SMALL]; int outdeg[MAXN]; int dfs_dist[MAXN]; bool dfs_visited[MAXN]; int jmp[MAXN][BIT]; int lg[MAXN]; int n; int lca(int a, int b) { if(dfs_dist[a] < dfs_dist[b]) swap(a, b); int diff = dfs_dist[a] - dfs_dist[b]; for(int i = 0; i < BIT; i++) { if((1 << i) & diff) a = jmp[a][i]; } if(a == b) return a; for(int i = BIT - 1; i >= 0; i--) { if(jmp[a][i] != jmp[b][i]) { a = jmp[a][i]; b = jmp[b][i]; } } return jmp[a][0]; } void dfs(int v, int p) { dfs_visited[v] = true; jmp[v][0] = p; for(int i = 1; i < BIT; i++) jmp[v][i] = jmp[jmp[v][i - 1]][i - 1]; for(int e : revadj[v]) { if(e == p || dfs_visited[e]) continue; dfs_dist[e] = dfs_dist[v] + 1; dfs(e, v); } } void init(int N, vector<int> H) { lg[1] = 0; for(int i = 2; i < MAXN; i++) lg[i] = lg[i / 2] + 1; n = N; stack<int> curr; for(int i = 0; i < N; i++) { if(H[i] != i + 1) sub1 = false; while(!curr.empty() && H[curr.top()] < H[i]) { int v = curr.top(); curr.pop(); adj[v].push_back(i); revadj[i].push_back(v); outdeg[v]++; } curr.push(i); } while(!curr.empty()) { curr.pop(); } for(int i = N - 1; i >= 0; i--) { while(!curr.empty() && H[curr.top()] < H[i]) { int v = curr.top(); curr.pop(); adj[v].push_back(i); revadj[i].push_back(v); outdeg[v]++; } curr.push(i); } int last = 0; for(int i = 0; i < N; i++) { if(outdeg[i] == 0) // We will have only one such node which is the biggest element in the array last = i; } dfs_dist[last] = 0; dfs(last, MAXN - 1); if(N <= 2000) { for(int i = 0; i < N; i++) { queue< int > ord; vector<bool> visited(N, false); dist[i][i] = 0; visited[i] = true; ord.push(i); while(!ord.empty()) { int v = ord.front(); ord.pop(); for(int e : revadj[v]) { if(visited[e]) continue; dist[e][i] = dist[v][i] + 1; visited[e] = true; ord.push(e); } } } /*for(int i = 0; i < N; i++) { for(int a = 0; a < N; a++) cout << i << " " << a <<": " << dist[i][a] << "\n"; }*/ for(int i = 0; i < N; i++) { for(int a = 0; a < N; a++) sparse[i][0][a] = dist[i][a]; for(int bit = 1; bit <= 11; bit++) { for(int j = 0; j + (1 << bit) - 1 < N; j++) { sparse[i][bit][j] = min(sparse[i][bit - 1][j], sparse[i][bit - 1][j + (1 << (bit - 1))]); //cout << i << " " << bit << " " << j << " " << sparse[i][bit][j] << "\n"; } } } } } int minimum_jumps(int A, int B, int C, int D) { if(sub1) // Subtask 1 { return C - B; } //Subtask 2, 3 if(n <= 2000) { int ans = 1e9; for(int i = A; i <= B; i++) { int add = lg[D - C + 1]; ans = min(ans, min(sparse[i][add][C], sparse[i][add][D - (1 << add) + 1])); //cout << i << " " << add << " " << sparse[i][add][C] << " " << sparse[i][add][D - (1 << add) + 1] << "\n"; } if(ans == 1e9) ans = -1; return ans; } if(C == D) { if(A == B) // Subtask 5 { int top = lca(A, C); if(top != A && top != C) return -1; //cout << dfs_dist[A] << " " << dfs_dist[C] << "\n"; return max(dfs_dist[A], dfs_dist[C]) - min(dfs_dist[A], dfs_dist[C]); } } //Subtask 4 vector<bool> visited(n, false); vector<int> dist(n, 1e9); queue<int> curr; for(int i = C; i <= D; i++) { dist[i] = 0; curr.push(i); visited[i] = true; } while(!curr.empty()) { int v = curr.front(); curr.pop(); for(int e : revadj[v]) { if(visited[e]) continue; visited[e] = true; dist[e] = dist[v] + 1; curr.push(e); } } int ans = 1e9; for(int i = A; i <= B; i++) ans = min(ans, dist[i]); if(ans == 1e9) ans = -1; return ans; }

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

jumps.cpp: In function 'void dfs(int, int)':
jumps.cpp:48:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |     if(e == p || dfs_visited[e])
      |     ^~
jumps.cpp:50:7: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   50 |       dfs_dist[e] = dfs_dist[v] + 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...