Submission #1033432

#TimeUsernameProblemLanguageResultExecution timeMemory
1033432ALeonidouSky Walking (IOI19_walk)C++17
10 / 100
1565 ms1048576 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define sz(x) (ll)x.size() #define F first #define S second #define endl "\n" #define INF 1000000000000000000 typedef vector <ll> vi; typedef pair <ll,ll> ii; typedef vector <ii> vii; typedef pair <ll, ii> iii; typedef vector <iii> viii; #define dbg(x) cout<<#x<<": "<<x<<endl; #define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl; #define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl; void printVct(vi &v){ for (ll i =0; i<sz(v); i++){ cout<<v[i]<<" "; } cout<<endl; } vector <vii> adj; vector <vii> v; //building, height vi x, h, l, r, y; ll s, g; ll new_node(ll building, ll y){ // dbg2(building, y); adj.pb(vii()); ll b = sz(adj)-1; adj[b].pb(ii(building, y)); adj[building].pb(ii(b, y)); for (ll i = 0; i<sz(v[building]); i++){ adj[v[building][i].F].pb(ii(b, abs(v[building][i].S-y))); adj[b].pb(ii(v[building][i].F, abs(v[building][i].S-y))); } v[building].pb(ii(b, y)); return sz(adj)-1; } vi dis; priority_queue <ii, vii, greater<ii> > pq; void dijkstra(ll s){ ll n = sz(adj); dis.assign(n, INF); dis[s] = 0; pq.push(ii(0, s)); ii f, v; ll c,w; while (!pq.empty()){ f = pq.top(); pq.pop(); c = f.S; w = f.F; if (dis[c] < w) continue; for (ll i =0; i<sz(adj[c]); i++){ v = adj[c][i]; if (v.S + dis[c] < dis[v.F]){ dis[v.F] = v.S + dis[c]; pq.push(ii(dis[v.F], v.F)); } } } } long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G) { s = S, g = G; ll n = sz(X), m = sz(L); x.resize(n), h.resize(n), l.resize(m), r.resize(m), y.resize(m); for (ll i =0; i<n; i++){ x[i] = X[i]; h[i] = H[i]; } viii bridges(m); for (ll i =0; i<m; i++){ y[i] = Y[i]; l[i] = L[i]; r[i] = R[i]; bridges[i] = iii(y[i], ii(l[i], r[i])); } sort(bridges.begin(), bridges.end()); for (ll i =0; i<m; i++){ y[i] = bridges[i].F; l[i] = bridges[i].S.F; r[i] = bridges[i].S.S; } //build graph adj.assign(n, vii()); v.assign(n, vii()); for (ll i = 0; i<m; i++){ ll curY = y[i]; // dbg(curY); ll lastR = -1; ll last_node, last_building; while (i < m && curY == y[i]){ ll l_pos = max(lastR, l[i]); ll r_pos = r[i]; if (l_pos >= r_pos) continue; // dbg2(l_pos, r_pos); if (lastR < l_pos){ last_node = new_node(l_pos, curY); last_building = l_pos; } for (ll j = l_pos+1; j<=r_pos; j++){ if (h[j] < curY) continue; ll cur_node = new_node(j, curY); // dbg3(j, cur_node, last_node); adj[last_node].pb(ii(cur_node, x[j] - x[last_building])); adj[cur_node].pb(ii(last_node, x[j] - x[last_building])); last_node = cur_node; last_building = j; } lastR = r_pos; i++; } i--; } // cout<<endl; // for (ll i =0; i<sz(adj); i++){ // cout<<i<<": "; // for (ll j =0; j<sz(adj[i]); j++){ // cout<<"("<<adj[i][j].F<<","<<adj[i][j].S<<") "; // } // cout<<endl; // } // for (ll i =0; i<sz(adj); i++){ // for (ll j =0; j<sz(adj[i]); j++){ // if (adj[i][j].F > i) // cout<<i<<" "<<adj[i][j].F<<" "<<adj[i][j].S<<endl; // } // } //sp dijkstra(s); ll ans = dis[g]; if (ans == INF){ ans = -1; } return ans; } /* 3 2 3 7 5 9 14 6 0 1 6 1 2 7 0 2 4 1 0 8 3 7 4 9 7 7 0 3 3 0 3 7 3 0 8 3 7 5 9 7 7 10 6 12 6 14 9 0 2 6 2 6 7 4 6 5 1 5 */

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:121:58: warning: 'last_building' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |     adj[last_node].pb(ii(cur_node, x[j] - x[last_building]));
      |                                                          ^
#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...