Submission #612738

#TimeUsernameProblemLanguageResultExecution timeMemory
612738definitelynotmeeSky Walking (IOI19_walk)C++17
24 / 100
1008 ms129344 KiB
#include "walk.h" #include<bits/stdc++.h> #define ff first #define ss second #define all(x) x.begin(),x.end() using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<typename T> using matrix = vector<vector<T>>; 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 from, int to) { int n = x.size(); int m = l.size(); bool ok = 1; for(int i = 1; i < n; i++){ ok&=h[i] == h[i-1]; } if(!ok){ int nodes = n; matrix<pii> lines; for(int i = 0; i < n; i++) lines.push_back({{0,i}}); set<int> s; vector<int> obuild(n), oline(m); iota(all(obuild),0); iota(all(oline),0); sort(all(obuild),[&](int a, int b){ return h[a] > h[b]; }); sort(all(oline),[&](int a, int b){ return y[a] > y[b]; }); int ptr = 0; for(int i : oline){ while(ptr < n && h[obuild[ptr]] >= y[i]) s.insert(obuild[ptr]), ptr++; vector<int> adj; auto it = s.lower_bound(l[i]); while(it!=s.end() && *it <= r[i]) adj.push_back(*it), it++; vector<pii> hor; for(int i = 0; i < adj.size(); i++){ hor.push_back({x[adj[i]],nodes+i}); } lines.push_back(hor); for(int j = 0; j < adj.size(); j++){ //cout << nodes+j << " = " << "(" << x[adj[j]] << ',' << y[i] << ")\n"; lines[adj[j]].push_back({y[i],nodes+j}); } nodes+=adj.size(); } matrix<pii> g(nodes); for(auto& i : lines){ sort(all(i)); for(int j = 1; j < i.size(); j++){ int peso = i[j].ff-i[j-1].ff; g[i[j-1].ss].push_back({i[j].ss,peso}); g[i[j].ss].push_back({i[j-1].ss,peso}); } } vector<ll> dist(nodes,1ll<<60); dist[from] = 0; priority_queue<pll,vector<pll>,greater<pll>> pq; pq.push({0,from}); while(!pq.empty()){ int cur = pq.top().ss; int curp = pq.top().ff; pq.pop(); if(curp > dist[cur]) continue; for(auto [viz,peso] : g[cur]){ if(dist[viz] > dist[cur]+peso){ dist[viz] = dist[cur]+peso; pq.push({dist[viz],viz}); } } } // for(int i = 0; i < nodes; i++) // cout << "->" << i << ": " << dist[i] << '\n'; if(dist[to] == (1ll<<60)) return -1; return dist[to]; } matrix<pii> g(m+2); // g[m] -> 0, g[m+1]->n-1 matrix<pii> op(n+1); for(int i = 0; i < m; i++){ op[l[i]].push_back({1,i}); op[r[i]+1].push_back({0,i}); if(l[i] == 0) g[m].push_back({i,y[i]}), g[i].push_back({m,y[i]}); if(r[i] == n-1) g[m+1].push_back({i,y[i]}), g[i].push_back({m+1,y[i]}); } set<pii> s; for(int i = 0; i < n; i++){ for(auto [type,id]: op[i]){ if(type){ auto it = s.lower_bound({y[id],id}); if(it != s.end()){ g[it->ss].push_back({id,abs(y[id]-it->ff)}); g[id].push_back({it->ss,abs(y[id]-it->ff)}); } if(it!=s.begin()){ it--; g[it->ss].push_back({id,abs(y[id]-it->ff)}); g[id].push_back({it->ss,abs(y[id]-it->ff)}); } s.insert({y[id],id}); } else { s.erase({y[id],id}); } } } vector<ll> dist(m+2,1ll<<60); dist[m] = 0; priority_queue<pll,vector<pll>,greater<pll>> pq; pq.push({0,m}); while(!pq.empty()){ int cur = pq.top().ss; int curp = pq.top().ff; pq.pop(); if(curp > dist[cur]) continue; for(auto [viz,peso] : g[cur]){ if(dist[viz] > dist[cur]+peso){ dist[viz] = dist[cur]+peso; pq.push({dist[viz],viz}); } } } // for(int i = 0; i < nodes; i++) // cout << "->" << i << ": " << dist[i] << '\n'; if(dist[m+1] == (1ll<<60)) return -1; return dist[m+1]+x.back()-x[0]; }

Compilation message (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:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for(int i = 0; i < adj.size(); i++){
      |                   ~~^~~~~~~~~~~~
walk.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int j = 0; j < adj.size(); j++){
      |                   ~~^~~~~~~~~~~~
walk.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    for(int j = 1; j < i.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...