제출 #295018

#제출 시각아이디문제언어결과실행 시간메모리
295018egekabasSky Walking (IOI19_walk)C++14
0 / 100
4086 ms46180 KiB
#include "walk.h" #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define ff first #define ss second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<int, int> pii; typedef pair<ld, ld> pld; struct sky{ int id, l, r, y; }; bool cmp(sky a, sky b){ if(a.y == b.y) return a.l < b.l; return a.y < b.y; } vector<int> godown[100009]; vector<int> goup[100009]; vector<ll> dis[100009]; long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){ vector<sky> tmp; for(int i = 0; i < l.size(); ++i) tmp.pb({i, l[i], r[i], y[i]}); sort(all(tmp), cmp); vector<sky> top; for(auto u : tmp){ if(top.size() && top.back().y == u.y && top.back().r == u.l) top.back().r = u.r; else top.pb(u); } vector<pii> add; vector<pii> era; for(int i = 0; i < top.size(); ++i){ top[i].id = i; add.pb({x[top[i].l], i}); era.pb({x[top[i].r]+1, i}); } sort(all(add), greater<pii>()); sort(all(era), greater<pii>()); set<pii> st; for(int i = 0; i < x.size(); ++i){ while(add.size() && add.back().ff <= x[i]){ st.insert({top[add.back().ss].y, add.back().ss}); add.pop_back(); } while(era.size() && era.back().ff <= x[i]){ st.erase({top[era.back().ss].y, era.back().ss}); era.pop_back(); } for(auto u : st){ if(u.ff > h[i]) break; godown[u.ss].pb(i); goup[i].pb(u.ss); } /*cout << i << '\n'; for(auto u : goup[i]) cout << top[u].l << ' ' << top[u].r << '\n';*/ sort(all(goup[i])); dis[i].resize(goup[i].size()+1, 1e18); } priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq; dis[s][0] = 0; pq.push({0, {s, 0}}); while(pq.size()){ ll d = pq.top().ff; ll id = pq.top().ss.ff; ll lev = pq.top().ss.ss; pq.pop(); if(dis[id][lev] < d) continue; for(ll i = 0; i < dis[id].size(); ++i){ ll nd = d; ll dissurf = 0; if(lev != 0) dissurf = top[goup[id][lev-1]].y; if(i == 0) nd += dissurf; else nd += abs(dissurf-top[goup[id][i-1]].y); if(nd < dis[id][i]){ dis[id][i] = nd; pq.push({nd, {id, i}}); } } if(lev == 0) continue; for(auto u : godown[goup[id][lev-1]]){ ll nd = d + abs(x[id]-x[u]); ll nl = lower_bound(all(goup[u]), goup[id][lev-1])-goup[u].begin()+1; if(nd < dis[u][nl]){ dis[u][nl] = nd; pq.push({nd, {u, nl}}); } } } return dis[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:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0; i < l.size(); ++i)
      |                 ~~^~~~~~~~~~
walk.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sky>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < top.size(); ++i){
      |                 ~~^~~~~~~~~~~~
walk.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 0; i < x.size(); ++i){
      |                 ~~^~~~~~~~~~
walk.cpp:80:19: 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]
   80 |   for(ll i = 0; i < dis[id].size(); ++i){
      |                 ~~^~~~~~~~~~~~~~~~
#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...