Submission #436525

#	Time	Username	Problem	Language	Result	Execution time	Memory
436525		rqi	Sky Walking (IOI19_walk)	C++14	0 / 100	191 ms	195172 KiB

walk

#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: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43