Submission #290329

#TimeUsernameProblemLanguageResultExecution timeMemory
290329MarcoMeijerSky Walking (IOI19_walk)C++14
43 / 100
4033 ms77736 KiB
#include <bits/stdc++.h> #include "walk.h" using namespace std; //macros typedef long long ll; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a:b) #define INF 1e18 #define pb push_back #define fi first #define se second #define sz size() #define all(a) a.begin(), a.end() ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) { int n=x.sz, m=l.sz, N=0; // change graph RE(j,2) { int x = j ? s : g; vi nl, nr, ny; priority_queue<iii> pq; RE(i,n) pq.push({h[i],2,i}); RE(i,m) { if(l[i] < x && x < r[i]) { pq.push({y[i],1,i}); } else { nl.pb(l[i]); nr.pb(r[i]); ny.pb(y[i]); } } int mostL = -1e9, mostR = 1e9; while(!pq.empty()) { iii p = pq.top(); pq.pop(); int y, t, i; tie(y,t,i) = p; if(t == 2) { if(i <= x) mostL = max(mostL, i); if(i >= x) mostR = min(mostR, i); } else if(t == 1) { if(mostL != l[i] ) nl.pb(l[i]) , nr.pb(mostL), ny.pb(y); if(mostL != mostR) nl.pb(mostL), nr.pb(mostR), ny.pb(y); if(r[i] != mostR) nl.pb(mostR), nr.pb(r[i]) , ny.pb(y); } } l=nl; r=nr; y=ny; m = l.sz; } l.pb(s); r.pb(s); y.pb(0); l.pb(g); r.pb(g); y.pb(0); m = l.sz; ll ans = INF; map<ii, int> vertexes; map<int, vi> horVertex; vector<vii> adj; auto getVert = [&](int x, int y) { if(vertexes.count({x,y})) return vertexes[{x,y}]; horVertex[y].pb(x); return vertexes[{x,y}] = N++; }; auto connect = [&](ii a, ii b) { int u = getVert(a.fi, a.se); int v = getVert(b.fi, b.se); int d = abs(a.fi-b.fi)+abs(a.se-b.se); adj[u].pb({v,d}); adj[v].pb({u,d}); }; adj.resize(m*4); // create vertexes, and vertical edges { priority_queue<iii> pq; multiset<int> st; RE(i,m) pq.push({r[i],2,i}); RE(i,m) pq.push({l[i],1,i}); RE(i,m) pq.push({r[i],1,i}); RE(i,m) pq.push({l[i],0,i}); while(!pq.empty()) { iii p = pq.top(); pq.pop(); int cx, t, i; tie(cx,t,i) = p; if(t == 2) { // right st.insert(y[i]); } else if(t == 1) { // connect getVert(x[cx], y[i]); auto it = st.lower_bound(y[i]); if(it != st.begin()) --it, connect({x[cx],y[i]}, {x[cx],*it}); } else { // left st.erase(st.find(y[i])); } } } // create horizontal edges { FOR(p,horVertex) sort(all(p.se)); RE(i,m) { if(l[i] == r[i]) continue; vi& f = horVertex[y[i]]; auto it=lower_bound(all(f), x[l[i]]); auto ed=upper_bound(all(f), x[r[i]]); while(1) { auto prev = it++; if(it == ed) break; connect({*prev, y[i]}, {*it, y[i]}); } } } // dijkstra { vll dist; dist.assign(N, INF); priority_queue<lll> pq; dist[getVert(x[s],0)] = 0; pq.push({getVert(x[s],0), 0}); while(!pq.empty()) { lll p = pq.top(); pq.pop(); int u=p.fi; ll d=p.se; if(dist[u] != d) continue; FOR(p,adj[u]) { int v = p.fi; ll add = p.se; if(d+add < dist[v]) { dist[v] = d+add; pq.push({v,dist[v]}); } } } ans = dist[getVert(x[g],0)]; } if(ans == INF) ans = -1; return ans; }
#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...