oj.uz

Submission #436512

# Submission time Handle Problem Language Result Execution time Memory
436512 2021-06-24T14:39:33 Z rqi Sky Walking (IOI19_walk) C++14
24 / 100
 4000 ms 458188 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);

	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 107 ms 141184 KB Output is correct
2 Correct 112 ms 141100 KB Output is correct
3 Correct 110 ms 141104 KB Output is correct
4 Correct 112 ms 141124 KB Output is correct
5 Correct 109 ms 141268 KB Output is correct
6 Correct 113 ms 141252 KB Output is correct
7 Correct 105 ms 141332 KB Output is correct
8 Correct 116 ms 141312 KB Output is correct
9 Correct 102 ms 141128 KB Output is correct
10 Correct 105 ms 141360 KB Output is correct
11 Correct 104 ms 141236 KB Output is correct
12 Correct 111 ms 141232 KB Output is correct
13 Correct 113 ms 141124 KB Output is correct
14 Correct 111 ms 141180 KB Output is correct
15 Correct 114 ms 141136 KB Output is correct
16 Correct 110 ms 141144 KB Output is correct
17 Correct 116 ms 141388 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 141176 KB Output is correct
2 Correct 109 ms 141176 KB Output is correct
3 Correct 2875 ms 328852 KB Output is correct
4 Correct 2657 ms 368484 KB Output is correct
5 Correct 1838 ms 339388 KB Output is correct
6 Correct 1637 ms 317448 KB Output is correct
7 Correct 1845 ms 339256 KB Output is correct
8 Correct 3809 ms 383264 KB Output is correct
9 Correct 2273 ms 334224 KB Output is correct
10 Correct 3653 ms 448520 KB Output is correct
11 Correct 1480 ms 252308 KB Output is correct
12 Correct 998 ms 236020 KB Output is correct
13 Correct 3057 ms 412472 KB Output is correct
14 Correct 670 ms 223120 KB Output is correct
15 Correct 771 ms 214592 KB Output is correct
16 Correct 752 ms 217000 KB Output is correct
17 Correct 793 ms 214628 KB Output is correct
18 Correct 757 ms 236620 KB Output is correct
19 Correct 125 ms 144800 KB Output is correct
20 Correct 326 ms 177080 KB Output is correct
21 Correct 787 ms 210488 KB Output is correct
22 Correct 772 ms 214812 KB Output is correct
23 Correct 639 ms 232996 KB Output is correct
24 Correct 727 ms 215072 KB Output is correct
25 Correct 862 ms 212596 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 160820 KB Output is correct
2 Execution timed out 4128 ms 458188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 160820 KB Output is correct
2 Execution timed out 4128 ms 458188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 141184 KB Output is correct
2 Correct 112 ms 141100 KB Output is correct
3 Correct 110 ms 141104 KB Output is correct
4 Correct 112 ms 141124 KB Output is correct
5 Correct 109 ms 141268 KB Output is correct
6 Correct 113 ms 141252 KB Output is correct
7 Correct 105 ms 141332 KB Output is correct
8 Correct 116 ms 141312 KB Output is correct
9 Correct 102 ms 141128 KB Output is correct
10 Correct 105 ms 141360 KB Output is correct
11 Correct 104 ms 141236 KB Output is correct
12 Correct 111 ms 141232 KB Output is correct
13 Correct 113 ms 141124 KB Output is correct
14 Correct 111 ms 141180 KB Output is correct
15 Correct 114 ms 141136 KB Output is correct
16 Correct 110 ms 141144 KB Output is correct
17 Correct 116 ms 141388 KB Output is correct
18 Correct 101 ms 141176 KB Output is correct
19 Correct 109 ms 141176 KB Output is correct
20 Correct 2875 ms 328852 KB Output is correct
21 Correct 2657 ms 368484 KB Output is correct
22 Correct 1838 ms 339388 KB Output is correct
23 Correct 1637 ms 317448 KB Output is correct
24 Correct 1845 ms 339256 KB Output is correct
25 Correct 3809 ms 383264 KB Output is correct
26 Correct 2273 ms 334224 KB Output is correct
27 Correct 3653 ms 448520 KB Output is correct
28 Correct 1480 ms 252308 KB Output is correct
29 Correct 998 ms 236020 KB Output is correct
30 Correct 3057 ms 412472 KB Output is correct
31 Correct 670 ms 223120 KB Output is correct
32 Correct 771 ms 214592 KB Output is correct
33 Correct 752 ms 217000 KB Output is correct
34 Correct 793 ms 214628 KB Output is correct
35 Correct 757 ms 236620 KB Output is correct
36 Correct 125 ms 144800 KB Output is correct
37 Correct 326 ms 177080 KB Output is correct
38 Correct 787 ms 210488 KB Output is correct
39 Correct 772 ms 214812 KB Output is correct
40 Correct 639 ms 232996 KB Output is correct
41 Correct 727 ms 215072 KB Output is correct
42 Correct 862 ms 212596 KB Output is correct
43 Correct 296 ms 160820 KB Output is correct
44 Execution timed out 4128 ms 458188 KB Time limit exceeded
45 Halted 0 ms 0 KB -