이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
const int nax = 1e6 + 3;
const long long INF = 1e18;
int n, m;
long long min_distance(vector<int> x, vector<int> h,
vector<int> l, vector<int> r, vector<int> y, int s, int g) {
n = x.size(), m = l.size();
map<int, vector<int>>row, col;
map<int, vector<int>>ens;
for(int i=0; i<m; ++i) {
ens[l[i]].push_back(y[i]);
ens[r[i]].push_back(-y[i]);
}
multiset<int>ms;
for(int i=0; i<n; ++i) {
for(int j : ens[i]) {
if(j>0) {
ms.insert(j);
}
}
for(int j : ms) {
if(j<=h[i]) {
row[j].push_back(x[i]);
col[x[i]].push_back(j);
} else break;
}
for(int j : ens[i]) {
if(j<0) {
ms.erase(ms.find(-j));
}
}
}
row[0].push_back(x[s]);
col[x[s]].push_back(0);
row[0].push_back(x[g]);
col[x[g]].push_back(0);
map<int, vector<int>>can;
for(auto &it : row) {
sort(it.second.begin(), it.second.end());
can[it.first].resize(it.second.size());
}
for(auto &it : col) {
sort(it.second.begin(), it.second.end());
}
for(int i=0; i<m; ++i) {
int j = lower_bound(row[y[i]].begin(), row[y[i]].end(), x[l[i]]) -
row[y[i]].begin();
while(row[y[i]][j]!=x[r[i]]) {
can[y[i]][j] = 1;
++j;
}
}
map<pair<int,int>,long long>dist;
for(auto it : row) {
for(int j : it.second) {
dist[{j, it.first}] = INF;
}
}
dist[{x[s], 0}] = 0;
priority_queue<tuple<long long, int,int>>pq;
pq.emplace(0, x[s], 0);
while(!pq.empty()) {
auto [w, x, y] = pq.top();
pq.pop();
w = -w;
if(w!=dist[{x, y}]) continue;
int j = lower_bound(row[y].begin(), row[y].end(), x) - row[y].begin();
if(j>0 && can[y][j-1]) {
int px = row[y][j-1];
if(dist[{px, y}]>w+x-px) {
dist[{px, y}] = w + x-px;
pq.emplace(-dist[{px, y}], px, y);
}
}
if(j+1<row[y].size() && can[y][j]) {
int nx = row[y][j+1];
if(dist[{nx, y}]>w+nx-x) {
dist[{nx, y}] = w + nx-x;
pq.emplace(-dist[{nx, y}], nx, y);
}
}
j = lower_bound(col[x].begin(), col[x].end(), y) - col[x].begin();
if(j>0) {
int py = col[x][j-1];
if(dist[{x, py}]>w+y-py) {
dist[{x, py}] = w + y-py;
pq.emplace(-dist[{x, py}], x, py);
}
}
if(j+1<col[x].size()) {
int ny = col[x][j+1];
if(dist[{x, ny}]>w+ny-y) {
dist[{x, ny}] = w + ny-y;
pq.emplace(-dist[{x, ny}], x, ny);
}
}
}
return dist[{x[g], 0}];
}
컴파일 시 표준 에러 (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:98:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | if(j+1<row[y].size() && can[y][j]) {
| ~~~^~~~~~~~~~~~~~
walk.cpp:115:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | if(j+1<col[x].size()) {
| ~~~^~~~~~~~~~~~~~
# | 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... |