#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge{
int l, r, y, idx;
Edge(){}
Edge(int l, int r, int y, int idx): l(l), r(r), y(y), idx(idx){}
bool operator<(const Edge &r)const{
if(y != r.y) return y < r.y;
return idx < r.idx;
}
};
int n, k, Start, Goal;
ll arr[100002];
ll height[100002];
ll el[100002], er[100002], ey[100002];
void findIntersections();
ll solve();
ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r,
vector<int> _y, int _s, int _t) {
n = (int)_x.size();
for(int i=1; i<=n; i++) arr[i] = _x[i-1], height[i] = _h[i-1];
k = (int)_l.size();
vector<Edge> vec;
for(int i=1; i<=k; i++) vec.push_back(Edge(_l[i-1] + 1, _r[i-1] + 1, _y[i-1], i));
sort(vec.begin(), vec.end());
for(int i=1; i<=k; i++) el[i] = vec[i-1].l, er[i] = vec[i-1].r, ey[i] = vec[i-1].y;
Start = _s+1, Goal = _t+1;
findIntersections();
return solve();
}
/// 정점과 간선 정보
int floorV[100002];
vector<pair<int, ll> > link[2000002];
vector<int> addLine[100002], delLine[100002];
vector<pair<int, int> > edgeIdx[100002]; /// 간선별로 정점을 추가할 x좌표들, 그리고 그 정점 번호
vector<pair<int, int> > towerIdx[100002]; /// x좌표별로 정점을 추가할 높이들, 그리고 그 정점 번호
int recent[100002];
vector<int> insertionPoint[100002];
void findIntersections(){
for(int i=1; i<=k; i++){
addLine[el[i]].push_back(i);
delLine[er[i]].push_back(i);
}
/// Subtask 4의 정점들만 추가
int vCnt = 0;
set<int> st; /// 간선 번호
for(int i=1; i<=n; i++){
for(int x: addLine[i]){
// printf("addLine %d - %d\n", i, x);
edgeIdx[x].push_back(make_pair(arr[i], ++vCnt));
towerIdx[i].push_back(make_pair(ey[x], vCnt));
// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[x]);
recent[x] = i;
auto it = st.insert(x).first;
if(it != st.begin() && recent[*prev(it)] != i){
int y = *prev(it);
edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
towerIdx[i].push_back(make_pair(ey[y], vCnt));
// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
recent[y] = i;
}
if(next(it) != st.end() && recent[*next(it)] != i){
int y = *next(it);
edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
towerIdx[i].push_back(make_pair(ey[y], vCnt));
// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
recent[y] = i;
}
}
for(int x: delLine[i]){
// printf("delLine %d - %d\n", i, x);
edgeIdx[x].push_back(make_pair(arr[i], ++vCnt));
towerIdx[i].push_back(make_pair(ey[x], vCnt));
// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[x]);
recent[x] = i;
auto it = st.find(x);
if(it != st.begin() && recent[*prev(it)] != i && arr[*prev(it)] <= ey[i]){
int y = *prev(it);
edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
towerIdx[i].push_back(make_pair(ey[y], vCnt));
// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
recent[y] = i;
}
if(next(it) != st.end() && recent[*next(it)] != i && arr[*next(it)] <= ey[i]){
int y = *next(it);
edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
towerIdx[i].push_back(make_pair(ey[y], vCnt));
// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
recent[y] = i;
}
st.erase(x);
}
towerIdx[i].push_back(make_pair(0, ++vCnt));
floorV[i] = vCnt;
// printf("%d: (%d, %d)\n", vCnt, arr[i], 0);
}
/// Full task의 정점들도 추가
st.clear();
for(int i=1; i<=n; i++){
auto it = prev(upper_bound(ey+1, ey+k, arr[i]));
if(it == ey) continue;
insertionPoint[it-ey].push_back(i);
}
for(int i=k; i>=1; i--){
for(int x: insertionPoint[i]){
st.insert(x);
}
auto it = st.lower_bound(Start);
if(it != st.end()){
int x = *it;
edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
towerIdx[x].push_back(make_pair(ey[i], vCnt));
// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
}
if(it != st.begin()){
int x = *prev(it);
edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
towerIdx[x].push_back(make_pair(ey[i], vCnt));
// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
}
it = st.lower_bound(Goal);
if(it != st.end()){
int x = *it;
edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
towerIdx[x].push_back(make_pair(ey[i], vCnt));
// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
}
if(it != st.begin()){
int x = *prev(it);
edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
towerIdx[x].push_back(make_pair(ey[i], vCnt));
// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
}
}
/// 정점들을 간선으로 연결
for(int i=1; i<=k; i++){
sort(edgeIdx[i].begin(), edgeIdx[i].end());
for(int j=0; j<(int)edgeIdx[i].size()-1; j++){
int x = edgeIdx[i][j].second, y = edgeIdx[i][j+1].second;
int v = edgeIdx[i][j+1].first - edgeIdx[i][j].first;
// printf("Connect %d %d : %d\n", x, y, v);
link[x].push_back(make_pair(y, v));
link[y].push_back(make_pair(x, v));
}
}
for(int i=1; i<=n; i++){
sort(towerIdx[i].begin(), towerIdx[i].end());
for(int j=0; j<(int)towerIdx[i].size()-1; j++){
int x = towerIdx[i][j].second, y = towerIdx[i][j+1].second;
int v = towerIdx[i][j+1].first - towerIdx[i][j].first;
// printf("Connect %d %d : %d\n", x, y, v);
link[x].push_back(make_pair(y, v));
link[y].push_back(make_pair(x, v));
}
}
}
struct dat{
int x; ll d;
dat(){}
dat(int x, ll d): x(x), d(d){}
bool operator<(const dat &r)const{
return d>r.d;
}
};
bool visited[2000002];
ll solve(){
// printf("Solve %d to %d\n", floorV[Start], floorV[Goal]);
priority_queue<dat> pq;
pq.push(dat(floorV[Start], 0));
while(!pq.empty()){
dat tmp = pq.top(); pq.pop();
if(visited[tmp.x]) continue;
if(tmp.x == floorV[Goal]) return tmp.d;
visited[tmp.x] = 1;
for(pair<int, ll> p: link[tmp.x]){
pq.push(dat(p.first, tmp.d + p.second));
}
}
// // printf("No solution\n");
return -1;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
58944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
59052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
242 ms |
101040 KB |
Output is correct |
| 2 |
Incorrect |
589 ms |
167448 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
242 ms |
101040 KB |
Output is correct |
| 2 |
Incorrect |
589 ms |
167448 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
58944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
