이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 7;
const int kN = 63;
vector<int> x, h, l, r, y;
vector<int> cross[kN];
int s, g, n, m;
vector<array<int, 3>> adj[kN][kN];
long long dist[kN][kN];
int find_in_cross(int idx, int val){
return lower_bound(cross[idx].begin(), cross[idx].end(), val) - cross[idx].begin();
}
long long dijkstra(int start1, int start2, int end1, int end2){
for(int i = 0; i < kN; ++i)
for(int j = 0; j < kN; ++j)
dist[i][j] = inf;
priority_queue<array<long long, 3>, vector<array<long long, 3>>, greater<array<long long, 3>>> pq;
dist[start1][start2] = 0;
pq.push({0, start1, start2});
while(!pq.empty()){
array<long long, 3> state = pq.top();
pq.pop();
int u1 = state[1], u2 = state[2];
if(state[0] != dist[u1][u2])
continue;
if(u1 == end1 && u2 == end2)
break;
for(auto edge: adj[u1][u2]){
int to1 = edge[0], to2 = edge[1];
if(dist[to1][to2] > dist[u1][u2] + edge[2]){
dist[to1][to2] = dist[u1][u2] + edge[2];
pq.push({dist[to1][to2], to1, to2});
}
}
}
return dist[end1][end2];
}
long long min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g){
x = _x, h = _h, l = _l, r = _r, y = _y, s = _s, g = _g;
n = x.size(), m = y.size();
sort(x.begin(), x.end());
for(int i = 0; i < m; ++i){
for(int j = l[i]; j <= r[i]; ++j){
if(h[j] >= y[i])
cross[j].push_back(y[i]);
}
}
for(int i = 0; i < n; ++i){
cross[i].push_back(0);
cross[i].push_back(h[i]);
}
for(int i = 0; i < n; ++i)
sort(cross[i].begin(), cross[i].end());
for(int i = 0; i < n; ++i){
vector<int> new_cross;
for(int j = 0; j < (int)cross[i].size() - 1; ++j){
if(cross[i][j] != cross[i][j + 1])
new_cross.push_back(cross[i][j]);
}
if(!cross[i].empty())
new_cross.push_back(cross[i].back());
cross[i] = new_cross;
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < (int)cross[i].size() - 1; ++j){
adj[i][j].push_back({i, j + 1, cross[i][j + 1] - cross[i][j]});
adj[i][j + 1].push_back({i, j, cross[i][j + 1] - cross[i][j]});
}
}
for(int i = 0; i < m; ++i){
int pr = -1;
for(int j = l[i]; j <= r[i]; ++j){
if(h[j] >= y[i]){
if(pr == -1){
pr = j;
continue;
}
int j_2 = find_in_cross(j, y[i]), pr_2 = find_in_cross(pr, y[i]);
adj[j][j_2].push_back({pr, pr_2, x[j] - x[pr]});
adj[pr][pr_2].push_back({j, j_2, x[j] - x[pr]});
pr = j;
}
}
}
long long ret = dijkstra(s, 0, g, 0);
if(ret == inf)
ret = -1;
return ret;
}
/*
5
3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
*/
# | 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... |