제출 #1071311

#제출 시각아이디문제언어결과실행 시간메모리
1071311LittleOrangeSky Walking (IOI19_walk)C++17
0 / 100
4091 ms646240 KiB
#include "walk.h" #include<bits/stdc++.h> using namespace std; using ll = long long; const ll big = 1e18; struct pos{ ll x,y; bool operator<(const pos &o) const{ return x!=o.x?x<o.x:y<o.y; } bool operator==(const pos &o) const{ return x==o.x&&y==o.y; } bool operator!=(const pos &o) const{ return x!=o.x||y!=o.y; } }; struct line{ ll i,v; bool operator<(const line &o) const{ return v>o.v; } }; 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) { ll n = x.size(); ll m = y.size(); vector<pos> ps; for(ll i = 0;i<n;i++) ps.push_back({x[i],0}); for(ll i = 0;i<m;i++){ for(ll j = l[i];j<=r[i];j++){ if (h[j]>=y[i]){ ps.push_back({x[j],y[i]}); } } } sort(ps.begin(),ps.end()); ps.erase(unique(ps.begin(),ps.end()),ps.end()); auto gp = [&](pos p){ return lower_bound(ps.begin(),ps.end(),p)-ps.begin(); }; ll c = ps.size(); vector<vector<line>> con(c); for(ll i = 1;i<c;i++){ if (ps[i-1].x==ps[i].x){ ll d = ps[i].y-ps[i-1].y; con[i-1].push_back({i,d}); con[i].push_back({i-1,d}); } } for(ll i = 0;i<m;i++){ vector<ll> v; for(ll j = l[i];j<=r[i];j++){ if (h[j]>=y[i]){ v.push_back(gp({x[j],y[i]})); } } for(ll j = 1;j<v.size();j++){ ll d = ps[v[j]].x-ps[v[j-1]].x; con[v[j-1]].push_back({v[j],d}); con[v[j]].push_back({v[j-1],d}); } } ll start = gp({x[s],0}); ll goal = gp({x[g],0}); vector<ll> dis(c,big); priority_queue<line> q; q.push({start,0}); while(q.size()){ auto [i,v] = q.top();q.pop(); if(dis[i]<=v) continue; dis[i] = v; for(auto [j,w] : con[i]){ q.push({j,v+w}); } } return dis[goal]; }

컴파일 시 표준 에러 (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:57:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(ll j = 1;j<v.size();j++){
      |                ~^~~~~~~~~
#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...