Submission #1206716

#TimeUsernameProblemLanguageResultExecution timeMemory
1206716thelegendary08Sky Walking (IOI19_walk)C++17
10 / 100
4094 ms41968 KiB
#include "walk.h" #include<bits/stdc++.h> #define int long long #define pb push_back #define mp make_pair #define f0r(i,n) for(int i = 0; i<n; i++) #define FOR(i, k, n) for(int i =k; i<n; i++) #define vi vector<int> #define pii pair<int,int> #define vvi vector<vector<int>> #define vb vector<bool> #define vpii vector<pii> #define mii map<int,int> #define dout(x) cout<<x<<' '<<#x<<endl; #define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl; #define out(x) cout<<x<<endl; #define out2(x,y) cout<<x<<' '<<y<<endl; using namespace std; const int mxn = (1e5 * 13); vector<vpii>adj(mxn); int min_distance(vector<signed> x, vector<signed> h, vector<signed> l, vector<signed> r, vector<signed> y, signed s, signed g) { //encode a position as h * n + i int n = x.size(); int m = l.size(); vvi pts(m); vector<pair<int,pair<pii,int>>>edges; f0r(i,m){ edges.pb(mp(y[i], mp(mp(l[i], r[i]),i))); } sort(edges.rbegin(), edges.rend()); set<int>active; vector<pair<int, pii>> nodes; f0r(i,n){ nodes.pb(mp(h[i], mp(x[i], i))); } sort(nodes.rbegin(), nodes.rend()); int p1 = 0; int p2 = 0; vi nxt(n, -1); while(p1 < m){ if(p2 == n){ auto it = lower_bound(active.begin(), active.end(), edges[p1].second.first.first); int cur = *it; int d = edges[p1].second.second; while(cur != -1 && cur <= edges[p1].second.first.second){ pts[d].pb(cur); cur = nxt[cur]; } p1++; } else{ if(edges[p1].first > nodes[p2].first){ //compute edge auto it = lower_bound(active.begin(), active.end(), edges[p1].second.first.first); int cur = *it; int d = edges[p1].second.second; while(cur != -1 && cur <= edges[p1].second.first.second){ pts[d].pb(cur); cur = nxt[cur]; } p1++; } else{ auto it = lower_bound(active.begin(), active.end(), nodes[p2].second.second); if(it != active.end())nxt[nodes[p2].second.second] = *it; if(it != active.begin()){ --it; nxt[*it] = nodes[p2].second.second; } active.insert(nodes[p2].second.second); p2++; } } } f0r(i,m){ sort(pts[i].begin(), pts[i].end()); } vector<vpii> ints(n); int cnt = n; f0r(i,m){ for(int k = 0; k<pts[i].size(); k++){ int j = pts[i][k]; ints[j].pb(mp(y[i], cnt)); cnt++; if(k > 0){ int j = pts[i][k-1]; int j2 = pts[i][k]; adj[cnt-1].pb(mp(cnt-2, x[j2] - x[j])); adj[cnt-2].pb(mp(cnt-1, x[j2] - x[j])); } } } f0r(i,n){ ints[i].pb(mp(0, i)); } f0r(i,n){ sort(ints[i].begin(), ints[i].end()); } f0r(i,n){ f0r(j, ints[i].size() - 1){ int h1 = ints[i][j].first; int h2 = ints[i][j+1].first; adj[ints[i][j].second].pb(mp(ints[i][j+1].second, h2-h1)); adj[ints[i][j+1].second].pb(mp(ints[i][j].second, h2-h1)); } } vi dist(mxn, 4e18); dist[s] = 0; priority_queue<pii>q; q.push(mp(0,s)); while(!q.empty()){ int node = q.top().second; q.pop(); for(auto u : adj[node]){ int b = u.first; int w = u.second; if(dist[b] > dist[node] + w){ dist[b] = dist[node] + w; q.push(mp(-dist[b], b)); } } } /* out(dist[n + 1]); out(dist[6 * n + 1]); out(dist[6 * n + 2]); out(dist[7*n+2]); out(dist[7*n+6]); out(dist[5*n+6]); out(dist[5*n+5]); */ if(dist[g] == 4e18)return -1; else return dist[g]; return 1; }
#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...