oj.uz

Submission #832729

# Submission time Handle Problem Language Result Execution time Memory
832729 2023-08-21T14:16:19 Z 79brue Sky Walking (IOI19_walk) C++17
25 / 100
 844 ms 153696 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));
		}
	}
}

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 27 ms 58964 KB Output is correct
2 Correct 28 ms 58964 KB Output is correct
3 Correct 27 ms 58960 KB Output is correct
4 Correct 29 ms 58996 KB Output is correct
5 Correct 28 ms 59052 KB Output is correct
6 Correct 28 ms 59084 KB Output is correct
7 Correct 28 ms 58980 KB Output is correct
8 Correct 28 ms 59052 KB Output is correct
9 Correct 27 ms 58960 KB Output is correct
10 Correct 28 ms 59092 KB Output is correct
11 Correct 28 ms 59024 KB Output is correct
12 Correct 28 ms 58956 KB Output is correct
13 Correct 28 ms 58976 KB Output is correct
14 Correct 28 ms 59048 KB Output is correct
15 Correct 27 ms 59008 KB Output is correct
16 Correct 28 ms 59044 KB Output is correct
17 Correct 29 ms 59092 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58984 KB Output is correct
2 Correct 28 ms 58964 KB Output is correct
3 Correct 265 ms 119520 KB Output is correct
4 Incorrect 410 ms 129876 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 132 ms 82040 KB Output is correct
2 Correct 441 ms 133272 KB Output is correct
3 Correct 608 ms 135564 KB Output is correct
4 Correct 603 ms 139532 KB Output is correct
5 Correct 844 ms 148324 KB Output is correct
6 Correct 696 ms 153696 KB Output is correct
7 Correct 315 ms 105648 KB Output is correct
8 Correct 290 ms 120964 KB Output is correct
9 Correct 768 ms 152328 KB Output is correct
10 Correct 348 ms 126772 KB Output is correct
11 Correct 46 ms 65688 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 82040 KB Output is correct
2 Correct 441 ms 133272 KB Output is correct
3 Correct 608 ms 135564 KB Output is correct
4 Correct 603 ms 139532 KB Output is correct
5 Correct 844 ms 148324 KB Output is correct
6 Correct 696 ms 153696 KB Output is correct
7 Correct 315 ms 105648 KB Output is correct
8 Correct 290 ms 120964 KB Output is correct
9 Correct 768 ms 152328 KB Output is correct
10 Correct 348 ms 126772 KB Output is correct
11 Correct 46 ms 65688 KB Output is correct
12 Correct 545 ms 135940 KB Output is correct
13 Correct 376 ms 136240 KB Output is correct
14 Correct 689 ms 144292 KB Output is correct
15 Correct 494 ms 131800 KB Output is correct
16 Correct 538 ms 131476 KB Output is correct
17 Correct 651 ms 139896 KB Output is correct
18 Correct 523 ms 131844 KB Output is correct
19 Correct 595 ms 131596 KB Output is correct
20 Correct 314 ms 106140 KB Output is correct
21 Correct 78 ms 73656 KB Output is correct
22 Correct 294 ms 123564 KB Output is correct
23 Correct 251 ms 122140 KB Output is correct
24 Correct 222 ms 117104 KB Output is correct
25 Correct 235 ms 119552 KB Output is correct
26 Correct 227 ms 117388 KB Output is correct
27 Correct 749 ms 145548 KB Output is correct
28 Correct 345 ms 136312 KB Output is correct
29 Correct 664 ms 145152 KB Output is correct
30 Correct 320 ms 105592 KB Output is correct
31 Correct 725 ms 153668 KB Output is correct
32 Correct 289 ms 119380 KB Output is correct
33 Correct 275 ms 122612 KB Output is correct
34 Correct 362 ms 132684 KB Output is correct
35 Incorrect 356 ms 128472 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58964 KB Output is correct
2 Correct 28 ms 58964 KB Output is correct
3 Correct 27 ms 58960 KB Output is correct
4 Correct 29 ms 58996 KB Output is correct
5 Correct 28 ms 59052 KB Output is correct
6 Correct 28 ms 59084 KB Output is correct
7 Correct 28 ms 58980 KB Output is correct
8 Correct 28 ms 59052 KB Output is correct
9 Correct 27 ms 58960 KB Output is correct
10 Correct 28 ms 59092 KB Output is correct
11 Correct 28 ms 59024 KB Output is correct
12 Correct 28 ms 58956 KB Output is correct
13 Correct 28 ms 58976 KB Output is correct
14 Correct 28 ms 59048 KB Output is correct
15 Correct 27 ms 59008 KB Output is correct
16 Correct 28 ms 59044 KB Output is correct
17 Correct 29 ms 59092 KB Output is correct
18 Correct 27 ms 58984 KB Output is correct
19 Correct 28 ms 58964 KB Output is correct
20 Correct 265 ms 119520 KB Output is correct
21 Incorrect 410 ms 129876 KB Output isn't correct
22 Halted 0 ms 0 KB -