이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//vector<pair<int,int>> adjlist[10000000]; // weight, node
vector<vector<pair<int,int>>> adjlist;
ll INF = 1e18;
ll dijkstra(int n, int a, int b){
vector<ll> distance(n);
for (int i = 0; i<n; i++){
distance[i]=INF;
}
distance[a]=0;
//priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
//pq.push({0,a});
set<pair<ll,int>> pq;
pq.insert({0,a});
while (pq.size()>0){
auto f = *pq.begin();
pq.erase(pq.begin());
if (f.first>distance[f.second]){continue;}
for (auto p : adjlist[f.second]){
if (distance[f.second]+p.first<distance[p.second]){
distance[p.second]=distance[f.second]+p.first;
pq.insert({distance[p.second],p.second});
}
}
}
return (distance[b]==INF)?-1:distance[b];
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
// x - horizontal distance
int n = x.size();
vector<int> coords = x;
sort(coords.begin(),coords.end());
vector<int> heights(n);
for (int i = 0; i<n; i++){
heights[i]=h[lower_bound(coords.begin(),coords.end(),x[i])-coords.begin()];
}
int m = l.size();
vector<int> inds(m);
for (int i = 0; i<m; i++){
inds[i]=i;
}
sort(inds.begin(),inds.end(),[y](int a, int b){return y[a]<y[b];});
int numnodes = 0;
vector<int> lastnode(n);
vector<int> lastheight(n,0);
adjlist.resize(n);
for (int i = 0; i<n; i++){
lastnode[i]=i;
}
vector<int> ind_order_height(n);
for (int i = 0; i<n; i++){
ind_order_height[i]=i;
//hinds.insert(i);
}
set<int> hinds(ind_order_height.begin(),ind_order_height.end());
sort(ind_order_height.begin(),ind_order_height.end(),[heights](int a, int b){return heights[a]<heights[b];});
int curnode = n;
int ptr = 0;
for (int i = 0; i<m; i++){
while (ptr<n&&heights[ind_order_height[ptr]]<y[inds[i]]){
hinds.erase(ind_order_height[ptr]);
ptr++;
}
// process skywalk inds[i]
int lc = l[inds[i]];
int rc = r[inds[i]];
//cout<<"process "<<lc<<' '<<rc<<'\n';
int prev = -1;
auto it = hinds.lower_bound(lc);
int lv = *it;
while (it!=hinds.end()&&(*it)<=rc){
int j = *it;
//cout<<"heights: "<<heights[j]<<'\n';
// link j to below
if (heights[j]<y[inds[i]]){assert(1==0);}
if (lastheight[j]!=y[inds[i]]){
//cout<<"connect "<<curnode<<' '<<lastnode[j]<<'\n';
adjlist.push_back(vector<pair<int,int>>());
adjlist[curnode].push_back({y[inds[i]]-lastheight[j],lastnode[j]});
adjlist[lastnode[j]].push_back({y[inds[i]]-lastheight[j],curnode});
lastnode[j]=curnode;
lastheight[j]=y[inds[i]];
curnode++;
}
// link j to left
if (j!=lv){
//cout<<"connect "<<lastnode[j]<<' '<<lastnode[prev]<<'\n';
adjlist[lastnode[j]].push_back({x[j]-x[prev],lastnode[prev]});
adjlist[lastnode[prev]].push_back({x[j]-x[prev],lastnode[j]});
}
prev = j;
it++;
}
//cout<<"bleh"<<endl;
}
if (n>10000){assert(1==0);}
return dijkstra(curnode,s,g);
}
컴파일 시 표준 에러 (stderr) 메시지
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:51:9: warning: unused variable 'numnodes' [-Wunused-variable]
51 | int numnodes = 0;
| ^~~~~~~~
# | 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... |