제출 #298702

#제출 시각아이디문제언어결과실행 시간메모리
298702eohomegrownappsSky Walking (IOI19_walk)C++14
10 / 100
4058 ms246588 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<pair<ll,int>> adjlist[10000000]; // weight, node 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; } set<int> hinds; vector<int> ind_order_height(n); for (int i = 0; i<n; i++){ ind_order_height[i]=i; hinds.insert(i); } 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<ll,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; } 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 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...