Submission #210908

#	Time	Username	Problem	Language	Result	Execution time	Memory
210908		oolimry	Sky Walking (IOI19_walk)	C++14	0 / 100	4073 ms	94300 KiB

walk

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

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

///To avoid confusion, 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) {
	int n = X.size(), m = L.size();
	walk skywalks[m];
	for(int i = 0;i < m;i++) skywalks[i] = {L[i], R[i], H[i]};
	
	vector<int> 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<int> aboveLine; ///A sweeping line going from bottom to top;
	
	vector<int> walkHeight; ///walk indeces sorted in increasing H
	for(int i = 0;i < m;i++) walkHeight.push_back(i);
	sort(walkHeight.begin(), walkHeight.end(), [&](int a, int b) { return H[a] < H[b]; });
	
	vector<ii> buildingHeight; ///building indeces soreted in increasing Y
	for(int i = 0;i < n;i++){
		buildingHeight.push_back(ii(Y[i], i));
		aboveLine.insert(i);
	}
	sort(buildingHeight.begin(), buildingHeight.end());
	int ptr = 0;
	
	for(int i = 0;i < m;i++){
		while(ptr < n && buildingHeight[ptr].first < H[i]){
			aboveLine.erase(buildingHeight[ptr].second);
			ptr++;
		}
		
		int w = walkHeight[i];		
		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[w].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<int> walkHeights;
	for(int 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<int> moreUseful; ///extra points to add to useful[i]
		for(int h : useful[i]){
			
			multiset<int>::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(int 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].back() > Y[i]) useful[i].pop_back(); ///critical point can't be above the building
	}
	
	vector<vertex> vertices;
	int S, E; ///Start and End based on renumbering
	int idx = 0;
	
	for(int i = 0;i < n;i++){
		if(i == START) S = idx;
		if(i == END) E = idx;
		for(int y : useful[i]){
			vertices.push_back({X[i], y, idx}); 
			idx++;
		}
	}
	
	
	//cout << S << " " << E << endl;
	int 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(int i = 0;i < N;i++){
		vertex v = vertices[i];
		cout << v.x << " " << v.y << " " << v.id << '\n';
	}
	//*/
	
	for(int 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));
		}
	}
	
	unordered_map<long long, vector<ii> > hori; ///vertices on the same line
	for(int i = 0;i < N;i++){
		hori[vertices[i].y].push_back(ii(vertices[i].x, vertices[i].id));
	}
	
	for(walk W : skywalks){
		vector<ii> V = hori[W.h];
		int pos = lower_bound(V.begin(), V.end(), ii(X[W.l],-1)) - V.begin();
		while(V[pos].first < X[W.r]){
			long long u = V[pos].second;
			long long v = V[pos+1].second;
			long long w = V[pos+1].first - V[pos].first;
			adj[u].push_back(ii(w,v));
			adj[v].push_back(ii(w,u));
			pos++;
		}
	}
	
	///Dijkstra
	priority_queue<ii, vector<ii>, less<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:105:9: warning: 'E' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int S, E; ///Start and End based on renumbering
         ^
walk.cpp:159:28: warning: 'S' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dij.push(ii(0,S)); vis[S] = 0;
                     ~~~~~~~^~~

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