제출 #775521

#제출 시각아이디문제언어결과실행 시간메모리
775521Abrar_Al_SamitSky Walking (IOI19_walk)C++17
0 / 100
2856 ms100880 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...