제출 #833122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833122		79brue	Sky Walking (IOI19_walk)	C++17	100 / 100	903 ms	187760 KiB

walk

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

using namespace std;

typedef long long ll;

struct Edge{
	int l, r, y, idx;
	Edge(){}
	Edge(int l, int r, int y, int idx): l(l), r(r), y(y), idx(idx){}
	bool operator<(const Edge &r)const{
		if(y != r.y) return y < r.y;
		return idx < r.idx;
	}
};

int n, k, Start, Goal;
ll arr[100002];
ll height[100002];
ll el[100002], er[100002], ey[100002];

void findIntersections();
ll solve();

ll min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r,
			    vector<int> _y, int _s, int _t) {
	n = (int)_x.size();
	for(int i=1; i<=n; i++) arr[i] = _x[i-1], height[i] = _h[i-1];
	k = (int)_l.size();

	vector<Edge> vec;
	for(int i=1; i<=k; i++) vec.push_back(Edge(_l[i-1] + 1, _r[i-1] + 1, _y[i-1], i));
	sort(vec.begin(), vec.end());
	
	for(int i=1; i<=k; i++) el[i] = vec[i-1].l, er[i] = vec[i-1].r, ey[i] = vec[i-1].y;
	
	Start = _s+1, Goal = _t+1;

	findIntersections();
	return solve();
}

/// 정점과 간선 정보
int floorV[100002];
vector<pair<int, ll> > link[2000002];
vector<int> addLine[100002], delLine[100002];

vector<pair<int, int> > edgeIdx[100002]; /// 간선별로 정점을 추가할 x좌표들, 그리고 그 정점 번호
vector<pair<int, int> > towerIdx[100002]; /// x좌표별로 정점을 추가할 높이들, 그리고 그 정점 번호
int recent[100002];

vector<int> insertionPoint[100002];

void findIntersections(){
	for(int i=1; i<=k; i++){
		addLine[el[i]].push_back(i);
		delLine[er[i]].push_back(i);
	}

	/// Subtask 4의 정점들만 추가
	int vCnt = 0;
	set<int> st; /// 간선 번호
	for(int i=1; i<=n; i++){
		for(int x: addLine[i]){
			// printf("addLine %d - %d\n", i, x);
			edgeIdx[x].push_back(make_pair(arr[i], ++vCnt));
			towerIdx[i].push_back(make_pair(ey[x], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[x]);
			recent[x] = i;

			auto it = st.insert(x).first;
			if(it != st.begin() && recent[*prev(it)] != i){
				int y = *prev(it);
				edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
				towerIdx[i].push_back(make_pair(ey[y], vCnt));
				// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
				recent[y] = i;
			}
			if(next(it) != st.end() && recent[*next(it)] != i){
				int y = *next(it);
				edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
				towerIdx[i].push_back(make_pair(ey[y], vCnt));
				// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
				recent[y] = i;
			}
		}
		for(int x: delLine[i]){
			// printf("delLine %d - %d\n", i, x);
			edgeIdx[x].push_back(make_pair(arr[i], ++vCnt));
			towerIdx[i].push_back(make_pair(ey[x], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[x]);
			recent[x] = i;

			auto it = st.find(x);
			if(it != st.begin()){
				int y = *prev(it);
				edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
				towerIdx[i].push_back(make_pair(ey[y], vCnt));
				// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
				recent[y] = i;
			}
			if(next(it) != st.end()){
				int y = *next(it);
				edgeIdx[y].push_back(make_pair(arr[i], ++vCnt));
				towerIdx[i].push_back(make_pair(ey[y], vCnt));
				// printf("%d: (%d, %d)\n", vCnt, arr[i], ey[y]);
				recent[y] = i;
			}
			st.erase(x);
		}
		towerIdx[i].push_back(make_pair(0, ++vCnt));
		floorV[i] = vCnt;
		// printf("%d: (%d, %d)\n", vCnt, arr[i], 0);
	}

	/// Full task의 정점들도 추가
	st.clear();
	for(int i=1; i<=n; i++){
		auto it = prev(upper_bound(ey+1, ey+k+1, height[i]));
		if(it == ey) continue;
		insertionPoint[it-ey].push_back(i);
		// printf("%d: bound %d (height[i] %d)\n", i, it-ey, height[i]);
	}
	for(int i=k; i>=1; i--){
		for(int x: insertionPoint[i]){
			// printf("Inserted %d in %d\n", x, i);
			st.insert(x);
		}

		auto it = st.lower_bound(Start);
		if(it != st.end() && el[i] <= *it && *it <= er[i]){
			int x = *it;
			edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
			towerIdx[x].push_back(make_pair(ey[i], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
		}
		if(it != st.begin() && el[i] <= *prev(it) && *prev(it) <= er[i]){
			int x = *prev(it);
			edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
			towerIdx[x].push_back(make_pair(ey[i], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
		}

		it = st.lower_bound(Goal);
		if(it != st.end() && el[i] <= *it && *it <= er[i]){
			int x = *it;
			edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
			towerIdx[x].push_back(make_pair(ey[i], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
		}
		if(it != st.begin() && el[i] <= *prev(it) && *prev(it) <= er[i]){
			int x = *prev(it);
			edgeIdx[i].push_back(make_pair(arr[x], ++vCnt));
			towerIdx[x].push_back(make_pair(ey[i], vCnt));
			// printf("%d: (%d, %d)\n", vCnt, arr[x], ey[i]);
		}
	}

	/// 정점들을 간선으로 연결
	for(int i=1; i<=k; i++){
		sort(edgeIdx[i].begin(), edgeIdx[i].end());
		for(int j=0; j<(int)edgeIdx[i].size()-1; j++){
			int x = edgeIdx[i][j].second, y = edgeIdx[i][j+1].second;
			int v = edgeIdx[i][j+1].first - edgeIdx[i][j].first;
			// printf("Connect %d %d : %d\n", x, y, v);
			link[x].push_back(make_pair(y, v));
			link[y].push_back(make_pair(x, v));
		}
	}

	for(int i=1; i<=n; i++){
		sort(towerIdx[i].begin(), towerIdx[i].end());
		for(int j=0; j<(int)towerIdx[i].size()-1; j++){
			// printf("i %d j %d arr[i] %d towerIdx[i][j+1].first %d\n", i, j, height[i], towerIdx[i][j+1].first);
			if(height[i] < towerIdx[i][j+1].first){
				//printf("Breaked because height[%d] = %d, towerIdx[%d][%d] = %d\n", i,height[i],i,j+1,towerIdx[i][j+1].first);
				break;
			}
			int x = towerIdx[i][j].second, y = towerIdx[i][j+1].second;
			int v = towerIdx[i][j+1].first - towerIdx[i][j].first;
			// printf("Connect %d %d : %d\n", x, y, v);
			link[x].push_back(make_pair(y, v));
			link[y].push_back(make_pair(x, v));
		}
	}
	assert(vCnt <= 2000000);
}

struct dat{
	int x; ll d;
	dat(){}
	dat(int x, ll d): x(x), d(d){}
	bool operator<(const dat &r)const{
		return d>r.d;
	}
};
bool visited[2000002];

ll solve(){
	// printf("Solve %d to %d\n", floorV[Start], floorV[Goal]);
	priority_queue<dat> pq;
	pq.push(dat(floorV[Start], 0));
	while(!pq.empty()){
		dat tmp = pq.top(); pq.pop();
		if(visited[tmp.x]) continue;
		// printf("%d: %lld\n", tmp.x, tmp.d);
		if(tmp.x == floorV[Goal]) return tmp.d;
		visited[tmp.x] = 1;

		for(pair<int, ll> p: link[tmp.x]){
			pq.push(dat(p.first, tmp.d + p.second));
		}
	}
	// // printf("No solution\n");
	return -1;
}

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