oj.uz

Submission #436522

# Submission time Handle Problem Language Result Execution time Memory
436522 2021-06-24T15:02:21 Z rqi Sky Walking (IOI19_walk) C++14
24 / 100
 4000 ms 454148 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;
typedef vector<ll> vl;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define bk back()
#define ins insert
#define lb lower_bound

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

const ll INF = 1e18;

int n, m;

const int mx = 2000005;
vector<pair<int, ll>> adj[mx];
ll dij[mx];

ll solveShort(int N, int A, int B){
	for(int i = 0; i < N; i++){
		dij[i] = INF;
	}

	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	dij[A] = 0;
	pq.push(mp(dij[A], A));

	while(sz(pq)){
		ll d = pq.top().f;
		int node = pq.top().s;
		pq.pop();
		if(dij[node] < d) continue;
		for(auto u: adj[node]){
			ll new_d = d+u.s;
			if(dij[u.f] <= new_d) continue;
			dij[u.f] = new_d;
			pq.push(mp(dij[u.f], u.f));
		}
	}

	if(dij[B] == INF) return -1;
	return dij[B];
}

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
	n = sz(x);
	m = sz(l);


	// if(s == 0 && g == n-1){
	// 	cout << "HI" << "\n";
	// 	cout.flush();
	// 	vi ending_at[mx];
	// 	for(int i = 0; i < m; i++){
	// 		ending_at[r[i]].pb(i);
	// 	}
	// 	vi starting_at[mx];
	// 	for(int i = 0; i < m; i++){
	// 		starting_at[l[i]].pb(i);
	// 	}

	// 	ending_at[0].pb(m);
	// 	starting_at[n-1].pb(m+1);
	// 	l.pb(0);
	// 	r.pb(0);
	// 	l.pb(n-1);
	// 	r.pb(n-1);

	// 	y.pb(0);
	// 	y.pb(0);

	// 	vector<pair<pi, ll>> eds;

	// 	set<pi> cur_sky_heights; // height, sky index
	// 	cur_sky_heights.ins(mp(m, y[m]));
	// 	for(int i = 0; i < n; i++){
	// 		//do updates
	// 		for(auto sky: ending_at[i]){
	// 			cur_sky_heights.erase(mp(y[sky], sky));
	// 		}
	// 		for(auto sky: starting_at[i]){
	// 			cur_sky_heights.ins(mp(y[sky], sky));
	// 		}

	// 		for(auto sky: ending_at[i]){
	// 			auto it_above = cur_sky_heights.lb(mp(y[sky], 0));
	// 			auto it_below = cur_sky_heights.lb(mp(y[sky]+1, 0));

	// 			if(it_above != cur_sky_heights.end()){
	// 				int to_sky = it_above->s;
	// 				eds.pb(mp(mp(sky, to_sky), abs(y[sky]-y[to_sky])));
	// 			}
	// 			if(it_below != cur_sky_heights.begin()){
	// 				it_below = prev(it_below);
	// 				int to_sky = it_below->s;
	// 				eds.pb(mp(mp(sky, to_sky), abs(y[sky]-y[to_sky])));
	// 			}
	// 		}
	// 	}

	// 	for(auto u: eds){
	// 		adj[u.f.f].pb(mp(u.f.s, u.s));
	// 	}

	// 	//m is source, m+1 is sink
	// 	return solveShort(m+2, m, m+1);
	// }

	vi sort_by_y;
	for(int i = 0; i < m; i++){
		sort_by_y.pb(i);
	}
	sort(all(sort_by_y), [&](const int& a, const int& b){
		return y[a] > y[b];
	});

	vi sort_by_h;
	for(int i = 0; i < n; i++){
		sort_by_h.pb(i);
	}
	sort(all(sort_by_h), [&](const int& a, const int& b){
		return h[a] > h[b];
	});

	set<int> active_buildings;

	int sort_by_h_ind = 0;

	vector<pair<pi, pi>> point_eds; //building index, height


	// cout << "HI" << "\n";
	// cout.flush();
	for(auto sky: sort_by_y){
		while(sort_by_h_ind < sz(sort_by_h)){
			int building_ind = sort_by_h[sort_by_h_ind];
			if(h[building_ind] >= y[sky]){
				active_buildings.ins(building_ind);
				sort_by_h_ind++;
			}
			else{
				break;
			}
		}

		auto it = active_buildings.lb(l[sky]);
		assert(*it == l[sky]);

		while(true){
			assert(next(it) != active_buildings.end());
			point_eds.pb(mp(mp(*it, y[sky]), mp(*next(it), y[sky])));

			if(*next(it) == r[sky]) break;

			it = next(it);
		}
	}


	// cout << "HI" << "\n";
	// cout.flush();
	set<int> each_building[mx]; //sky walk heights for each building
	for(auto u: point_eds){
		// cout << u.f.f << " " << u.f.s << " " << u.s.f << " " << u.s.s << "\n";
		each_building[u.f.f].ins(u.f.s);
		each_building[u.s.f].ins(u.s.s);
	}

	for(int i = 0; i < n; i++){
		each_building[i].ins(0);
		each_building[i].ins(h[i]);
	}

	for(int i = 0; i < n; i++){
		auto it = each_building[i].begin();
		while(next(it) != each_building[i].end()){

			int y1 = *it;
			int y2 = *next(it);
			point_eds.pb(mp(mp(i, y1), mp(i, y2)));

			it = next(it);
		}
	}

	map<pi, int> compress;
	vpi all_nodes;
	for(auto u: point_eds){
		all_nodes.pb(u.f);
		all_nodes.pb(u.s);
	}
	int cnt = 0;
	for(auto u: all_nodes){
		if(!compress.count(u)){
			compress[u] = cnt;
			cnt++;
		}
	}

	// for(auto u: point_eds){
	// 	cout << u.f.f << " " << u.f.s << " " << u.s.f << " " << u.s.s << "\n";
	// }
	for(auto u: point_eds){
		ll dist = INF;
		if(u.f.f == u.s.f){
			dist = abs(u.s.s-u.f.s);
		}
		else{
			assert(u.s.s == u.f.s);
			dist = abs(x[u.s.f]-x[u.f.f]);
		}
		int a = compress[u.f];
		int b = compress[u.s];
		adj[a].pb(mp(b, dist));
		adj[b].pb(mp(a, dist));

		// cout << a << " " << b << " " << dist << "\n";
	}


	return solveShort(cnt, compress[mp(s, 0)], compress[mp(g, 0)]);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 141160 KB Output is correct
2 Correct 102 ms 141128 KB Output is correct
3 Correct 99 ms 141172 KB Output is correct
4 Correct 101 ms 141120 KB Output is correct
5 Correct 93 ms 141296 KB Output is correct
6 Correct 95 ms 141268 KB Output is correct
7 Correct 96 ms 141252 KB Output is correct
8 Correct 104 ms 141328 KB Output is correct
9 Correct 94 ms 141168 KB Output is correct
10 Correct 93 ms 141380 KB Output is correct
11 Correct 97 ms 141244 KB Output is correct
12 Correct 98 ms 141128 KB Output is correct
13 Correct 105 ms 141124 KB Output is correct
14 Correct 103 ms 141200 KB Output is correct
15 Correct 94 ms 141168 KB Output is correct
16 Correct 94 ms 141184 KB Output is correct
17 Correct 97 ms 141460 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 141120 KB Output is correct
2 Correct 103 ms 141180 KB Output is correct
3 Correct 3428 ms 329564 KB Output is correct
4 Correct 2942 ms 365132 KB Output is correct
5 Correct 1757 ms 336684 KB Output is correct
6 Correct 1558 ms 314860 KB Output is correct
7 Correct 1976 ms 336656 KB Output is correct
8 Correct 3839 ms 382160 KB Output is correct
9 Correct 2134 ms 331468 KB Output is correct
10 Correct 3806 ms 445444 KB Output is correct
11 Correct 1485 ms 251184 KB Output is correct
12 Correct 1012 ms 233932 KB Output is correct
13 Correct 3275 ms 410336 KB Output is correct
14 Correct 770 ms 221756 KB Output is correct
15 Correct 829 ms 213652 KB Output is correct
16 Correct 791 ms 216340 KB Output is correct
17 Correct 909 ms 214328 KB Output is correct
18 Correct 748 ms 236392 KB Output is correct
19 Correct 127 ms 144704 KB Output is correct
20 Correct 328 ms 177004 KB Output is correct
21 Correct 821 ms 210068 KB Output is correct
22 Correct 838 ms 213904 KB Output is correct
23 Correct 638 ms 232420 KB Output is correct
24 Correct 785 ms 214328 KB Output is correct
25 Correct 879 ms 212276 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 160896 KB Output is correct
2 Execution timed out 4083 ms 454148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 160896 KB Output is correct
2 Execution timed out 4083 ms 454148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 141160 KB Output is correct
2 Correct 102 ms 141128 KB Output is correct
3 Correct 99 ms 141172 KB Output is correct
4 Correct 101 ms 141120 KB Output is correct
5 Correct 93 ms 141296 KB Output is correct
6 Correct 95 ms 141268 KB Output is correct
7 Correct 96 ms 141252 KB Output is correct
8 Correct 104 ms 141328 KB Output is correct
9 Correct 94 ms 141168 KB Output is correct
10 Correct 93 ms 141380 KB Output is correct
11 Correct 97 ms 141244 KB Output is correct
12 Correct 98 ms 141128 KB Output is correct
13 Correct 105 ms 141124 KB Output is correct
14 Correct 103 ms 141200 KB Output is correct
15 Correct 94 ms 141168 KB Output is correct
16 Correct 94 ms 141184 KB Output is correct
17 Correct 97 ms 141460 KB Output is correct
18 Correct 98 ms 141120 KB Output is correct
19 Correct 103 ms 141180 KB Output is correct
20 Correct 3428 ms 329564 KB Output is correct
21 Correct 2942 ms 365132 KB Output is correct
22 Correct 1757 ms 336684 KB Output is correct
23 Correct 1558 ms 314860 KB Output is correct
24 Correct 1976 ms 336656 KB Output is correct
25 Correct 3839 ms 382160 KB Output is correct
26 Correct 2134 ms 331468 KB Output is correct
27 Correct 3806 ms 445444 KB Output is correct
28 Correct 1485 ms 251184 KB Output is correct
29 Correct 1012 ms 233932 KB Output is correct
30 Correct 3275 ms 410336 KB Output is correct
31 Correct 770 ms 221756 KB Output is correct
32 Correct 829 ms 213652 KB Output is correct
33 Correct 791 ms 216340 KB Output is correct
34 Correct 909 ms 214328 KB Output is correct
35 Correct 748 ms 236392 KB Output is correct
36 Correct 127 ms 144704 KB Output is correct
37 Correct 328 ms 177004 KB Output is correct
38 Correct 821 ms 210068 KB Output is correct
39 Correct 838 ms 213904 KB Output is correct
40 Correct 638 ms 232420 KB Output is correct
41 Correct 785 ms 214328 KB Output is correct
42 Correct 879 ms 212276 KB Output is correct
43 Correct 285 ms 160896 KB Output is correct
44 Execution timed out 4083 ms 454148 KB Time limit exceeded
45 Halted 0 ms 0 KB -