제출 #171706

#제출 시각아이디문제언어결과실행 시간메모리
171706dsjongSky Walking (IOI19_walk)C++14
10 / 100
4128 ms823136 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; map<pair<long long,long long>,long long> mp; vector<pair<long long,long long>>adj[1000005]; long long dis[1000005]; long long INF=LONG_LONG_MAX; bool vis[1000005]; void dijkstra(long long source){ class prioritize{ public: bool operator ()(pair<long long,long long>&p1 ,pair<long long,long long>&p2){ return p1.second>p2.second; } }; for(long long i=0;i<=1000000;i++) dis[i]=INF; priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,prioritize>pq; dis[source]=0; pq.push({source,0}); while(!pq.empty()){ pair<long long,long long>curr=pq.top(); pq.pop(); long long cv=curr.first,cw=curr.second; if(vis[cv]) continue; vis[cv]=true; for(auto i:adj[cv]){ if(vis[i.first]) continue; if(i.second+cw<dis[i.first]){ dis[i.first]=i.second+cw; //cout<<i.first<<" "<<dis[i.first]<<endl; pq.push({i.first,dis[i.first]}); } } } } long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) { vector<pair<long long,long long>>all; long long n = x.size(), m = l.size(); mp[{s,0}]=0; mp[{g,0}]=1; long long cnt = 2; all.push_back({s,0}); all.push_back({g,0}); for(long long i = 0; i < m; i++){ long long last=-1; for(long long j = l[i]; j <= r[i]; j++){ if(!mp[{j, y[i]}] && h[j] >= y[i]){ all.push_back({j, y[i]}); mp[{j, y[i]}] =cnt; //cout<<mp[{j,y[i]}]<<endl; cnt++; } if(h[j]>=y[i]){ if(last!=-1){ adj[mp[{j,y[i]}]].push_back({mp[{last,y[i]}],x[j]-x[last]}); adj[mp[{last,y[i]}]].push_back({mp[{j,y[i]}],x[j]-x[last]}); //cout<<mp[{j,y[i]}]<<" "<<mp[{last,y[i]}]<<" "<<x[j]-x[last]<<endl; } last = j; } } } //cout<<e; sort(all.begin(),all.end()); for(long long i=1; i < all.size(); i++){ if(all[i].first == all[i-1].first){ adj[mp[all[i]]].push_back({mp[all[i-1]], all[i].second-all[i-1].second}); adj[mp[all[i-1]]].push_back({mp[all[i]], all[i].second-all[i-1].second}); } } dijkstra(0); if(dis[1]==INF) return -1; return dis[1]; }

컴파일 시 표준 에러 (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:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(long long i=1; i < all.size(); i++){
                     ~~^~~~~~~~~~~~
walk.cpp:38:12: warning: unused variable 'n' [-Wunused-variable]
  long long n = x.size(), m = l.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...