이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |