oj.uz

Submission #832733

# Submission time Handle Problem Language Result Execution time Memory
832733 2023-08-21T14:17:55 Z 79brue Sky Walking (IOI19_walk) C++17
25 / 100
 793 ms 149640 KB 
#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() && recent[*prev(it)] != i && arr[*prev(it)] <= ey[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 && arr[*next(it)] <= ey[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;
			}
			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) 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 58964 KB Output is correct
2 Correct 26 ms 58968 KB Output is correct
3 Correct 27 ms 59068 KB Output is correct
4 Correct 27 ms 58952 KB Output is correct
5 Correct 27 ms 59000 KB Output is correct
6 Correct 32 ms 59088 KB Output is correct
7 Correct 27 ms 58956 KB Output is correct
8 Correct 27 ms 58980 KB Output is correct
9 Correct 27 ms 59052 KB Output is correct
10 Correct 28 ms 59064 KB Output is correct
11 Correct 28 ms 59048 KB Output is correct
12 Correct 27 ms 59072 KB Output is correct
13 Correct 26 ms 59024 KB Output is correct
14 Correct 26 ms 58948 KB Output is correct
15 Correct 28 ms 58960 KB Output is correct
16 Correct 27 ms 59008 KB Output is correct
17 Correct 27 ms 59068 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 59020 KB Output is correct
2 Correct 27 ms 58924 KB Output is correct
3 Correct 265 ms 117560 KB Output is correct
4 Incorrect 395 ms 127672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 81956 KB Output is correct
2 Correct 440 ms 133280 KB Output is correct
3 Correct 583 ms 133432 KB Output is correct
4 Correct 605 ms 135120 KB Output is correct
5 Correct 793 ms 144232 KB Output is correct
6 Correct 654 ms 149596 KB Output is correct
7 Correct 324 ms 102664 KB Output is correct
8 Correct 272 ms 116908 KB Output is correct
9 Correct 781 ms 148352 KB Output is correct
10 Correct 342 ms 123368 KB Output is correct
11 Correct 46 ms 64952 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 81956 KB Output is correct
2 Correct 440 ms 133280 KB Output is correct
3 Correct 583 ms 133432 KB Output is correct
4 Correct 605 ms 135120 KB Output is correct
5 Correct 793 ms 144232 KB Output is correct
6 Correct 654 ms 149596 KB Output is correct
7 Correct 324 ms 102664 KB Output is correct
8 Correct 272 ms 116908 KB Output is correct
9 Correct 781 ms 148352 KB Output is correct
10 Correct 342 ms 123368 KB Output is correct
11 Correct 46 ms 64952 KB Output is correct
12 Correct 549 ms 133932 KB Output is correct
13 Correct 387 ms 132276 KB Output is correct
14 Correct 750 ms 140312 KB Output is correct
15 Correct 529 ms 127940 KB Output is correct
16 Correct 536 ms 127484 KB Output is correct
17 Correct 666 ms 135620 KB Output is correct
18 Correct 545 ms 128020 KB Output is correct
19 Correct 619 ms 127544 KB Output is correct
20 Correct 330 ms 103104 KB Output is correct
21 Correct 76 ms 71668 KB Output is correct
22 Correct 279 ms 119852 KB Output is correct
23 Correct 254 ms 118304 KB Output is correct
24 Correct 233 ms 113332 KB Output is correct
25 Correct 240 ms 115912 KB Output is correct
26 Correct 220 ms 113744 KB Output is correct
27 Correct 785 ms 141544 KB Output is correct
28 Correct 439 ms 132388 KB Output is correct
29 Correct 670 ms 141196 KB Output is correct
30 Correct 328 ms 102664 KB Output is correct
31 Correct 670 ms 149640 KB Output is correct
32 Correct 296 ms 116252 KB Output is correct
33 Correct 290 ms 119488 KB Output is correct
34 Correct 375 ms 129564 KB Output is correct
35 Incorrect 340 ms 125316 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 58964 KB Output is correct
2 Correct 26 ms 58968 KB Output is correct
3 Correct 27 ms 59068 KB Output is correct
4 Correct 27 ms 58952 KB Output is correct
5 Correct 27 ms 59000 KB Output is correct
6 Correct 32 ms 59088 KB Output is correct
7 Correct 27 ms 58956 KB Output is correct
8 Correct 27 ms 58980 KB Output is correct
9 Correct 27 ms 59052 KB Output is correct
10 Correct 28 ms 59064 KB Output is correct
11 Correct 28 ms 59048 KB Output is correct
12 Correct 27 ms 59072 KB Output is correct
13 Correct 26 ms 59024 KB Output is correct
14 Correct 26 ms 58948 KB Output is correct
15 Correct 28 ms 58960 KB Output is correct
16 Correct 27 ms 59008 KB Output is correct
17 Correct 27 ms 59068 KB Output is correct
18 Correct 28 ms 59020 KB Output is correct
19 Correct 27 ms 58924 KB Output is correct
20 Correct 265 ms 117560 KB Output is correct
21 Incorrect 395 ms 127672 KB Output isn't correct
22 Halted 0 ms 0 KB -