oj.uz

Submission #1033432

# Submission time Handle Problem Language Result Execution time Memory
1033432 2024-07-24T20:21:47 Z ALeonidou Sky Walking (IOI19_walk) C++17
10 / 100
 1565 ms 1048576 KB 
#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

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]));
      |                                                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 860 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 1565 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18416 KB Output is correct
2 Runtime error 1287 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18416 KB Output is correct
2 Runtime error 1287 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 860 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Runtime error 1565 ms 1048576 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -