Submission #211003

#	Time	Username	Problem	Language	Result	Execution time	Memory
211003		oolimry	Sky Walking (IOI19_walk)	C++14	100 / 100	1259 ms	119388 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> ii;
long long inf = (1LL << 62LL);

///X, Y refers to points & buildings. L, R, H refers to skywalks
struct walk { long long l, r, h; };
struct vertex { long long x, y, id; };

long long min_distance(vector<int> X, vector<int> Y, vector<int> L, vector<int> R, vector<int> H, int START, int END) {
	long long n = X.size(), m = L.size();
	walk skywalks[m];
	for(long long i = 0;i < m;i++) skywalks[i] = {L[i], R[i], H[i]};
	
	vector<long long> useful[n];
	useful[START].push_back(0);
	useful[END].push_back(0);
	
	for(walk w : skywalks){
		useful[w.l].push_back(w.h);
		useful[w.r].push_back(w.h);
	}
	
	///For skywalks crossing START and END, Split them
	set<long long> aboveLine; ///A sweeping line going from bottom to top;
	
	vector<long long> walkHeight; ///walk indeces sorted in increasing H
	for(long long i = 0;i < m;i++) walkHeight.push_back(i);
	sort(walkHeight.begin(), walkHeight.end(), [&](long long a, long long b) { return H[a] < H[b]; });
	
	vector<ii> buildingHeight; ///building indeces soreted in increasing Y
	for(long long i = 0;i < n;i++){
		buildingHeight.push_back(ii(Y[i], i));
		aboveLine.insert(i);
	}
	sort(buildingHeight.begin(), buildingHeight.end());
	long long ptr = 0;
	
	for(long long i = 0;i < m;i++){
		long long w = walkHeight[i];
		while(ptr < n && buildingHeight[ptr].first < H[w]){
			aboveLine.erase(buildingHeight[ptr].second);
			ptr++;
		}
		
		if(L[w] <= START && START <= R[w]){
			auto it = aboveLine.lower_bound(START);
			if(*it == START){
				useful[START].push_back(H[w]);
			}
			else{
				useful[*it].push_back(H[w]);
				it--;
				useful[*it].push_back(H[w]);
			}
		}
		
		if(L[w] <= END && END <= R[w]){
			auto it = aboveLine.lower_bound(END);
			if(*it == END){
				useful[END].push_back(H[w]);
			}
			else{
				useful[*it].push_back(H[w]);
				it--;
				useful[*it].push_back(H[w]);
			}
		}
		
	}
	
	vector<ii> event[n]; ///process walks from left to right
	for(walk w : skywalks){
		event[w.l].push_back(ii(w.h, 1));
		if(w.r != n-1) event[w.r+1].push_back(ii(w.h, -1));
	}
	
	multiset<long long> walkHeights;
	for(long long i = 0;i < n;i++){ 
		for(ii Ev : event[i]){
			if(Ev.second == 1) walkHeights.insert(Ev.first);
			else walkHeights.erase(walkHeights.find(Ev.first));
		}
		
		vector<long long> moreUseful; ///extra points to add to useful[i]
		
		for(long long h : useful[i]){
			multiset<long long>::iterator it = walkHeights.upper_bound(h);
			//if(it != walkHeights.end()) moreUseful.push_back(*it);
			if(it == walkHeights.begin()) continue;
			it--;
			if(it != walkHeights.begin()) moreUseful.push_back(*(--it));
		}
		
		for(long long u : moreUseful) useful[i].push_back(u);
		sort(useful[i].begin(),useful[i].end());
		useful[i].erase(unique(useful[i].begin(),useful[i].end()), useful[i].end());
		while(useful[i].size() > 0 && useful[i].back() > Y[i]) useful[i].pop_back();
	}
	
	
	vector<vertex> vertices;
	long long S, E; ///Start and End based on renumbering
	long long idx = 0;
	
	for(long long i = 0;i < n;i++){
		if(i == START) S = idx;
		if(i == END) E = idx;
		for(long long y : useful[i]){
			vertices.push_back({X[i], y, idx}); 
			idx++;
		}
	}
	
	long long N = vertices.size(); ///big N is for no. of nodes on the graph
	vector<ii> adj[N];
	long long vis[N];
	fill(vis, vis + N, inf);
	
	for(long long i = 1;i < N;i++){
		if(vertices[i].x == vertices[i-1].x){
			long long w = vertices[i].y - vertices[i-1].y;
			adj[i].push_back(ii(w,i-1));
			adj[i-1].push_back(ii(w,i));
		}
	}
	
	auto compY = [&](vertex a, vertex b){ return ii(a.y,a.x) < ii(b.y,b.x); };
	sort(vertices.begin(),vertices.end(),compY);
	
	for(walk w : skywalks){
		int pos = lower_bound(vertices.begin(),vertices.end(), (vertex){X[w.l], w.h, -1} ,compY) - vertices.begin();
		while(vertices[pos].x < X[w.r]){
			long long u = vertices[pos].id;
			pos++;
			long long v = vertices[pos].id;
			long long w = vertices[pos].x - vertices[pos-1].x;
			adj[u].push_back(ii(w,v));
			adj[v].push_back(ii(w,u));
		}
	}
	
	///Dijkstra
	priority_queue<ii, vector<ii>, greater<ii> > dij;
	dij.push(ii(0,S)); vis[S] = 0;
	while(!dij.empty()){
		ii u = dij.top(); dij.pop();
		for(ii v : adj[u.second]){
			if(vis[v.second] > u.first + v.first){
				vis[v.second] = u.first + v.first;
				dij.push(ii(vis[v.second], v.second));
			}
		}
	}
	
	if(vis[E] >= inf) vis[E] = -1;
	return vis[E];
}

Compilation message (stderr)

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:147:28: warning: 'S' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dij.push(ii(0,S)); vis[S] = 0;
                     ~~~~~~~^~~
walk.cpp:105:15: warning: 'E' may be used uninitialized in this function [-Wmaybe-uninitialized]
  long long S, E; ///Start and End based on renumbering
               ^

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43