oj.uz

Submission #436510

# Submission time Handle Problem Language Result Execution time Memory
436510 2021-06-24T14:38:29 Z rqi Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 318616 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 = 100005;
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 6 ms 7244 KB Output is correct
2 Correct 6 ms 7244 KB Output is correct
3 Correct 6 ms 7372 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 7 ms 7500 KB Output is correct
6 Correct 7 ms 7512 KB Output is correct
7 Correct 7 ms 7500 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 6 ms 7372 KB Output is correct
10 Correct 7 ms 7500 KB Output is correct
11 Correct 6 ms 7372 KB Output is correct
12 Correct 6 ms 7372 KB Output is correct
13 Correct 6 ms 7372 KB Output is correct
14 Correct 6 ms 7384 KB Output is correct
15 Correct 6 ms 7244 KB Output is correct
16 Correct 6 ms 7372 KB Output is correct
17 Correct 7 ms 7500 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7252 KB Output is correct
2 Correct 6 ms 7244 KB Output is correct
3 Runtime error 1690 ms 275144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 27672 KB Output is correct
2 Execution timed out 4107 ms 318616 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 27672 KB Output is correct
2 Execution timed out 4107 ms 318616 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 6 ms 7244 KB Output is correct
3 Correct 6 ms 7372 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 7 ms 7500 KB Output is correct
6 Correct 7 ms 7512 KB Output is correct
7 Correct 7 ms 7500 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 6 ms 7372 KB Output is correct
10 Correct 7 ms 7500 KB Output is correct
11 Correct 6 ms 7372 KB Output is correct
12 Correct 6 ms 7372 KB Output is correct
13 Correct 6 ms 7372 KB Output is correct
14 Correct 6 ms 7384 KB Output is correct
15 Correct 6 ms 7244 KB Output is correct
16 Correct 6 ms 7372 KB Output is correct
17 Correct 7 ms 7500 KB Output is correct
18 Correct 7 ms 7252 KB Output is correct
19 Correct 6 ms 7244 KB Output is correct
20 Runtime error 1690 ms 275144 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -